sri ramanuja seva

This lesson is an introduction to recursion. (See here for more posts on C Programming.)

In this lesson, we shall get introduced to recursion in C. Pls see the above images for learning through illustrative images.
Recursion is a nice technique, which helps in solving complex problems using just few lines of code. Just as loops allow us to solve complex-looking problems using just few lines of code, recursion also accomplishes the same.

In recursion, we express the problem in terms of smaller subproblems of the same type. And then, in turn, the smaller subproblems are expressed in terms of still more smaller subproblems of the same type. By solving the small subproblems, the big problem gets solved.

A recursive function is a function which calls itself.

Two things to keep in mind when designing recursive function –
– What is the recursive formula? (That is, how to express the problem in terms of smaller subproblems of the same type?)
– What is the base case? (That is, when should the recursion terminate? For what case do we directly know the answer?)

Example. Design a recursive function to compute 5 + 4 + 3 + 2 + 1.
Solution.
We can see that 5 + 4 + 3 + 2 + 1 is the same as 5 + (4 + 3 + 2 + 1).
Again, 4 + 3 + 2 + 1 is the same as 4 + (3 + 2 + 1).

(We’re trying to break down the problem to be solved into smaller subproblems of the same type.)

Let Sum(n) denote the sum n + (n-1) + (n-2) + … + 1.
So, Sum(5) is 5 + 4 + 3 + 2 + 1. Sum(4) is 4 + 3 + 2 + 1. And so on.

We can write: Sum(5) is 5 + Sum(4).
Similarly, we have that: Sum(4) is 4 + Sum(3).
Similarly, Sum(3) is 3 + Sum(2).
Similarly, Sum(2) is 2 + Sum(1),
Sum(1) is simply directly 1.

In general, we have that: Sum(n) is equal to n + Sum(n-1).
This is the recursive formula. (We’ve expressed the problem (Sum(n)) in terms of a smaller subproblem of the same type (Sum(n-1)).

And, Sum(1) is 1.
This is the base case.

Let’s try to code this logic:

#include <stdio.h> 
int AddSeries(int n) //recursive function to find n + (n-1) + ... + 1
{
    return n + AddSeries(n-1); 
}
int main()
{
     int answer = AddSeries(3); 
     printf("The sum is %d. \n", answer); 
     return 0; 
}

The above recursive function has a big problem – The function execution will never terminate.
AddSeries(3) will call AddSeries(2), which will in turn call AddSeries(1), which will call AddSeries(0), which will call AddSeries(-1), and so on.
Solution – In the function body, we need to add a base case, to ensure that the recursion stops at some point.
As we already saw earlier, a base case is that AddSeries(1) is 1.

Here’s the modified correct code:

#include <stdio.h> 
int AddSeries(int n) //recursive function to find n + (n-1) + ... + 1
{
      if (n == 1)       //base case 
          return 1; 
  
      return n + AddSeries(n-1);    //recursive formula 
}
int main()
{
     int answer = AddSeries(3);  //call the function with argument as 3. 
     printf("The sum is %d. \n", answer); 
     return 0; 
}

output: 
The sum is 6. 

Explanation of the code: (How does the program work?)
– In Line 13, AddSeries() function is called with argument 3. So, we now execute the AddSeries() code with value of n as 3.
– The condition in Line 5 is false (3 is not equal to 1). Hence, we skip Line 6, and go to Line 8. In Line 8, there is a call to AddSeries(2). So, now the AddSeries() function code again starts getting executed. This time argument is 2.
– The condition in Line 5 is false.. (2 is not equal to 1.) We go to Line 8.. Now, there is a call to AddSeries(1). So, now the AddSeries() code again starts getting executed, this time with argument 1.
– The condition in Line 5 is true. Therefore, AddSeries(1) returns the value 1 (Line 6).
– AddSeries(1) was called in Line 8 of the AddSeries(2) execution. So, we go there. AddSeries(2) returns 2 + 1, which is 3.
– AddSeries(2) was called by Line 8 of AddSeries(3). So, now we go back there. So, now AddSeries(3) returns 3 + AddSeries(2), which is 3 + 3, which is 6.
– AddSeries(3) was called in Line 13 of the program. AddSeries(3) returns the value 6. This is stored in the variable answer, which is then displayed in Line 14. This completes the program.

Summary:

• Recursion is a technique in which we solve a problem by expressing it in terms of smaller subproblems of the same type.
• A recursive function is a function which calls itself.
• Two things to keep in mind when designing recursive solutions –
  – What is the recursive formula? (That is, how to express the problem in terms of smaller subproblems of the same type?)
  – What is the base case? (That is, when should the recursion stop? For what case do we directly know the answer?)

(For the next part of this tutorial on recursion, pls see here: Recursion – Part 2.)