Common recursion examples for beginners in C

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. This can be a very powerful tool in writing algorithms.
Let's understand it with a real life scenario.
Suppose you are lost in place and want to return to your hotel. What will you do now? You will definitely seek for help and ask someone near you to tell the path back to hotel.

Let's call it a function find hotel

function "find hotel"
1. Ask stranger which path to go  (they tell you : -> "that way")
2. Move that way until unsure.
3. Again find hotel

You go through with this until you see your hotel.

Doing the same thing again and again resulting in minimizing the distance between you and your hotel until there comes a point you don't have to ask as you have reached your hotel.

Let's see this in technical terms. All recursive algorithms must have the following : 

1. Base case ( definition of when to stop )
2. Work until you reach base case (small steps)
3. Recursive calls (i.e., when you repeat the process with a smaller subset of the problem)

Now we should some basic problems in order to get more comfortable with recursion

1. Print n to 1 with recursion

As discussed above all recursive problems have 3 stages let's find out the 3 stages for this problem.

1. Base case: We are asked to print n to 1, so 1 is the last digit to print after 1 we have to stop our program. So, if n get to 0 we should stop.
2. Work until you reach base case: Our work is to print numbers, so print n.
3. Recursive calls: Every time we print a number we start reducing it to get to 1. So we again call the function with the value n-1.

Code:

//C Code
#include<stdio.h>
int printWithRecursion(int n)
{
    if(n==0) //base case
    return 0;
    else{
        printf("%d ",n); // step 2
        printWithRecursion(n-1); //recursive call to start again
    }
}
int main()
{
    int n = 5;
    printWithRecursion(n);
    return 0;
}

Explanation: The flow of the code goes like: if n!=0 print n, 5 gets printed. Again the same function is called now with n-1 = 4, if 4!=0 4 gets printed and so on until n == 0 then the function stops.

For example if function call happens first with n = 3.

if n!=0 print n i.e. 3 is printed after that again function is getting called for n-1 i.e. n = 2 value. Again n is checked if it's equal to zero or not, so 2 is not equal to 0 hence 2 is printed, now the function is again getting called with n-1 i.e. n = 1 value, 1 is not equal to 0 so after getting printed, further function call is happening this time n-1 = 1-1 = 0, so the base condition is true here and we the function ends.

As an exercise you can try to print 1 to N.

2. Sum of 1 to n numbers

If n = 5, sum = 15 (1+2+3+4+5).

Let's discuss the steps: 
1. Base case: We are asked to get the sum from 1 to n, we have to reduce n every time until n = 1 after that we have to stop. So, that becomes our base case.
2. Work until you reach base case: Our work is to add numbers.
3. Recursive calls: Every time do the sum of the numbers  we start reducing n till it gets to 1.  So we again call the function with the value n-1. 

Code:

//C Code
#include<stdio.h>
int sumWithRecursion(int n)
{  
    if(n==0) //base case 1st step
    return 0;
    else{
        return  n + sumWithRecursion(n-1); //2nd and 3rd step together   
    }
}
int main()
{
   int n = 5;
   int ans =  sumWithRecursion(n);
   printf("%d",ans);
   return 0;
}

Explanation: Since, we have passed n = 5 to the function sumWithRecursion(), thus if the value of n would have been 0 then 0 would have been returned by the base case as an answer. Otherwise if the integer n is greater than 1, then
 n + sumWithRecursion(n-1) is called that  add's n with the sum of (n-1). Now the function is called with value of n-1 i.e., n = 4, and 4 is greater then 0, again sumWithRecursion() is called with value n-1 i.e. n = 3.

Now, this happens until we reach n=0, i.e. after 3 more calls the value of n will be equal to 0 then the base condition is satisfied and value 0 is returned.

Now the answer is not returned to the main function but to the previous function call happened when n was equal to 1 to complete the function.

1 + sumWithRecursion(0), since we got the answer as 0 when function was called with value 0 so, when n = 1, the answer is 1 + 0 = 1. Now 1 is returned to the previous call of n = 2 to complete the function call of 2 + sumWithRecursion(1), so 2 + 1 = 3. Now 3 is returned to the function call of n = 3, i.e. 3 + sumWithRecursion(2)  i.e. 3 + 3 = 6, now 6 is returned to the function call made when n = 4, i.e. 4 + sumWithRecursion(3) = 4 + 6  = 10. Now 10 is returned to the call happened when n = 5, i.e. 5 + sumWithRecursion(4) and it gets computed with value 5 + 10 = 15, and then there are no previous calls of sumWithRecursion() left, so the answer 15 get's returned to the main.

Note : If you are thinking why it works that is because in a recursive algorithm, the computer "remembers" every previous state of the problem. This information is "held" by the computer on the "activation stack" (i.e., inside of each functions workspace). Every function has its own workspace PER CALL of the function.

3. Find the factorial of a number N

If n = 4, then ans = 24 ( 4 X 3 X 2 X 1 = 24)

It's almost like the above problem. And you would have most probably find out the three cases by now. 

One important thing is we should take care to what are we returning from our base case. We know we have to stop after n = 1. But if we return 0 then the answer would get to 0. So, we have to return 1 as multiplication of 0 with any number is 0 and multiplication of a number with 1 is always the number itself. 

Code:

//C Code
#include<stdio.h>
int fact(int n)
{   
    if(n==0 || n==1) //base case 1st step
    return 1;
    else{
        return  n * fact(n-1); //2nd and 3rd step together
    }
}
int main()
{
   int n = 4;
   int ans =  fact(n);
   printf("%d",ans);
   return 0;
}

Explanation: Suppose we  pass a value  n to the function factorial. Thus, if the value of the integer n is 0 or 1, return 1; will return 1. Otherwise if the integer n is greater than 1, then n*fact(n-1); multiplies n with the factorial of n-1.

Now, let's take value n = 4, if the number is 4, then n*fact(n-1) implies 4*fact(3). So by writing 'n*fact(n-1)', we are again calling the function 'fact' inside itself. Now the same function is called with the new value of n = 3. The function call keep happening until a base condition is satisfied and then we get a value. Like if the value of n is 1 we are returned 1 as an answer, and if the value is 0 we are again returned 1.

Now, if we call the function with value n = 2, this time else part is getting executed since n is greater 1, so in else block we call  return n*fact(n-1)' i.e. 2*fact(1). So, it will again call 'fact' with value of n as 1, now with n = 1, it's our base case so 1 is returned to the function call made previously with n = 2, so we can compute the value of fact(1) = 1, hence 2*fact(1) = 2 * 1 = 2, so value of 2 factorial is 2.

Now, try this with 3. This time, it will return 3*fact(2). Again it will call fact(2) which will return 2*fact(1). So the expression will be return 3*2*fact(1) which is 3*2*1 ( since fact(1) will return 1 ). 
For 4, the expression will be 4*fact(3). Calling fact(3) will return 4*3*fact(2) ( since fact(3) will return 3*fact(2) ). Again calling fact(2) will return 4*3*2*fact(1). Thus, at last, 4*3*2*1 or 24 will be returned.

4. Print the n-th Fibonacci number:

In mathematics, the Fibonacci numbers, commonly denoted Fn, form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

The beginning of the sequence is : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.

Here F1 = 0, and F2 = 1 and Fn = sum of previous two numbers i.e. F(n-1) + F(n-2)

So, as per the definition we know we have to start with F1 and F2 with set values, or we can say F1 and F2 can be our multiple base cases. 

And our work is to do the sum of previous F values.

Code: 

//C Code
#include<stdio.h>
int fib(int n)
{   
    if(n == 0) // base case 1 i.e. F1
      return 0;
    else if(n == 1) //base case 2 i.e. F2
      return 1;
    else 
      return (fib(n-1) + fib(n-2)); // recursive calls
   
}
int main()
{
   int n = 9;
   int ans =  fib(n);
   printf("%d",ans);
   return 0;
}

We first check if the number n is zero or one. If yes, we return the value of n. If not, we recursively call fibonacci with the values n-1 and n-2.

As an example, if we wanted to calculate fibonacci(3), we know from the definition of the Fibonacci sequence that: fibonacci(3) = fibonacci(2) + fibonacci(1) . 

And, using the recursive method, we get to the line of code above which reflects this definition: fibonacci(2) + fibonacci(1) . And fibonacci(2) can be further written as :  (fibonacci(1) + fibonacci(0)) + fibonacci(1) , which leads us to the end result 
fibonacci(3) = (fibonacci(1) + fibonacci(0)) + fibonacci(1), which evaluates/resolves to: fibonacci(3) = 1 + 0 + 1 = 2. And the reason why the first logic checks for less than 2 is because we already know that the fibonacci series starts with 0, 1, 1 according to the rule.

Lastly, with recursion we try to break down a more complex problem into a simple step towards the solution and a remainder that is an easier version of the same problem. We can then repeat this process, taking the same step towards the solution each time, until we reach a version of our problem with a very simple solution (referred to as a base case). The simple solution to our base case aggregated with the steps we took to get there then form a solution to our original problem.