What is Recursion

A function calling itself. Well that's what most of us know.
But something that will help a beginner with recursion is that recursion follows a Mathematical concept that is PMI - Principle of Mathematical Induction. For those who are afraid of maths this'll be a punch. But to know more about this we have to imagine how recursion works...

Calculate Sum of Digits of a Number

Imagine I have a number 123 and we need to calculate the sum of individual digit in this number i.e. 1+2+3 = 6.
We can do this iteratively easily, using for and while loops. But in recursion we take a Base case that'll return some integer like

#include <bits/stdc++.h>
using namespace std;

int SumOfDigits(int number){
  // Base case
  if (number==0){
    return 0;
  };
  // Recursion & Calculation
  number = SumOfDigits(number/10)+(number%10);
  return number;
};

Here what base case is doing :

 // Base case
  if (number==0){
    return 0;
  };

We know that once number gets to 0 it'll return 0. That means that if my number reaches end of the digit.
We are splitting the whole number into smaller numbers that's what recursion is about, split your problem into the smaller problems. Once you find the answer to smaller problems you'll find your answer to main problem eventually.

What we did here:

  // Recursion & Calculation
  number = SumOfDigits(number/10)+(number%10);
  return number;

We split number without last digit every time recursion is called. Once there will be only one digit left say - 1, this is where our base case comes into action, as 1/10 will give 0 and it'll eventually return answer to be 0. In manner 12 will be solved as base case of 1 returns 0 we added first and last digit of the number i.e. 1+2 = 3. Once this is done consecutive recursion will split 3 and 3, now as the previous recursion returned 3, we again added last and first value i.e. 3+3 = 6.
This might be somewhat tough to understand in the beginning, but once you get practice of this by dry running your code in paper you'll start to understand it even more.

NOTE

One more reason why we used base case to be 0 before conclusion, is that since our recursion doesn't stops by itself and it keeps making the number shorter this will give Runtime error or Segmentation fault at sometime. To avoid this we added a base case that's returning 0 once there is only one element is left in the number.
Hope this helps to get a little clear image of recursion. Keep practicing it on problems and you'll get through it.