sri ramanuja seva

Recursion lesson – continued.
(For Part 2 of this series, pls see here: Recursion Tutorial Part 2.)
In this lesson, we’ll use recursion to write a function to compute the n-th term of the Fibonacci series. Pls see the images below.

Pls see the above images. The same content is given in text format below.

Q. If we are given a problem, and we want to design a recursive solution for it, how would we proceed?
Answer.

• We’ll see how we can break down the problem into smaller problems of the same type. That gives us the recursive formula.
• And, in order to ensure that the recursion eventually stops, we need to figure out an appropriate base case.

Q. What if we forget to have a base case?
Answer.
The solution will not work. The recursive computations will never. A base case is needed in order to terminate the recursion.

Q. Once we have the recursive formula and the base case, how do we translate that into C code?
Answer.

• We will define a recursive function. We’ll give it an appropriate name which indicates what it does.
• In the function definition, we’ll code the base case.
• We’ll also code the recursive formula. (We’ll call the same function on a smaller input.)
• In the main() function, we’ll call the recursive function on the appropriate input.

Fibonacci series

Fibonacci series is sequence of numbers where each term is the sum of the previous two terms.
For instance, the 10th term of the Fibonacci series is the sum of the 9th term of the series and the 8th term of the series.
Similarly, the 9th term of the series is the sum of the 8th term and the 7th term.

The first two terms of the series are fixed as 0 and 1.
That is, the 1st term of the Fibonacci series is 0. And the 2nd term of the Fibonacci series is 1.

• Let Fib(n) denote the n-th term of the Fibonacci series.
• Fib(1) is 0, and Fib(2) is 1.
• Fib(3) is Fib(1) + Fib(2), which is 1 + 0, which is 1.
• Fib(4) is Fib(3) + Fib(2), which is 1 + 1, which is 2.
• Fib(5) is Fib(4) + Fib(3), which is 2 + 1, which is 3.
• Fib(6) is Fib(5) + Fib(4), which is 3 + 2, which is 5.
• Fib(7) is Fib(6) + Fib(5), which is 5 + 3, which is 8.
• And so on, we can compute each Fibonacci term as the sum of the previous two terms.

Q. Let’s say we want to find Fib(20). How will we proceed to write a program for it?
Answer.
We can see that Fib(n) is Fib(n-1) + Fib(n-2). This gives us the recursive formula.
And we know that, Fib(1) is 0, and Fib(2) is 1. These give us our base cases.
Using the recursive formula and base cases, we can easily define a recursive function. That will enable us to compute any Fibonacci term we want.

//Program to find n-th term of Fibonacci series, recursively 
#include <stdio.h>
int Fib(int n) //recursive function; returns n-th term of Fib series 
{
    if (n==1)
        return 0;  //base case: 1st term of Fib series is 0. 
    if (n==2)
        return 1; //another base case: 2nd term of Fib series is 1. 
    return Fib(n-1) + Fib(n-2); //recursive formula. 
}
int main()
{
    int n; //which Fib term to find 
    printf("Pls enter which Fibonacci term you want to find: ");
    scanf("%d", &n); 
    
    printf("Term %d of Fib series is %d.", n, Fib(n)); //call the function. 
    return 0;
}

Sample output: 
Pls enter which Fibonacci term you want to find: 4 
Term 4 of Fib series is 2. 
Sample output: 
Pls enter which Fibonacci term you want to find: 8 
Term 8 of Fib series is 13. 

Q. Why do we need two base cases? What if we just have one base case: Fib(1) is 0.
Answer.
The solution will not work. The recursive function will never terminate.
For instance, let’s assume there’s a call to Fib(3). It will in turn call Fib(2) and Fib(1).
Fib(2) will in turn call Fib(1) and Fib(0).
Now, Fib(1) is known to us through the base case, but Fib(0) is not.
Fib(0) will in turn call Fib(-1) and Fib(-2), and so on, this will keep on going.
So, in order to ensure that the recursion terminates, we need two base cases.

Recap: what we learnt in this lesson-

• We saw how recursion can be used to compute the nth term of the Fibonacci series.
• We also saw that there can multiple base cases, and not just one.

(For Part 1 of the tutorial on recursion in C, pls see here: Recursion tutorial – Part 1)
(For posts related to C Programming, pls see here: C Programming.)