Recursive Functions

RECURSIVE FUNCTIONS

A recursive function is defined as a function that calls itself to solve a smaller version of its task until a final call is made which does not require a call to itself. Every recursive solution has two major cases:

• Base case, in which the problem is simple enough to be solved directly without making any further calls to the same function.

• Recursive case, in which first the problem at hand is divided into simpler sub-parts. Second the function calls itself but with sub-parts of the problem obtained in the first step. Third, the result is obtained by combining the solutions of simpler sub-parts.

Therefore, recursion is defining a large and complex problem in terms of smaller and more easily solvable problems. In recursive function, a complex problem is defined in terms of simpler problems and the simplest problem is given explicitly.

To understand recursive functions, let us take an example of calculating factorial of a number. To calculate n!, we multiply the number with factorial of the number that is 1 less than that number. In other words,  n ! = n × (n-1)!

Let us say we need to find the value of 5!.

5! = 5 × 4 × 3 × 2 × 1

= 120

This can be written as

5! = 5 × 4!, where 4!= 4 × 3!

Therefore,

5! = 5 × 4 × 3!

Similarly, we can also write,

5! = 5 × 4 × 3 × 2!

Expanding further

5! = 5 × 4 × 3 × 2 × 1!

We know, 1! = 1

Therefore, the series of problems and solutions can be given as shown in Figure 4.6.

Now if you look at the problem carefully, you can see that we can write a recursive function to calculate the factorial of a number. Every recursive function must have a base case and a recursive case. For the factorial function,

• Base case is when n = 1, because if n = 1, the result will be 1 as 1! = 1.

• Recursive case of the factorial function will call itself but with a smaller value of n, this case can be given as

factorial (n) = n × factorial (n-1)

Look at the following code which calculates the factorial of a number recursively.

Programming Tip: Every recursive function must have at least one base case. Otherwise, the recursive function will generate an infinite sequence of calls thereby resulting in an error condition known as an infinite stack.

#include <stdio.h>

int Fact (int);

int main()

{

int num, factorial;

printf("\n Enter the number: ");

scanf("%d", &num);

factorial = Fact (num);

printf("\n Factorial of %d = %d", num, factorial);

return 0;

}

int Fact (int n)

{

if (n==1)

return 1;

else

return (n* Fact (n-1));

}

From the above example, let us analyse the basic steps of a recursive program.

Step 1: Specify the base case which will stop the function from making a call to itself.

Step 2: Check to see whether the current value being processed matches with the value of the base case. If yes, process and return the value.

Step 3: Divide the problem into smaller or simpler sub-problems.

Step 4: Call the function from the sub-problems. 

Step 5: Combine the results of the sub-problems. 

Step 6: Return the result of the entire problem.

Note

The base case of a recursive function acts as the terminating condition. So, in the absence of an explicitly- defined base case, a recursive function would call itself indefinitely.

Greatest Common Divisor

The greatest common divisor (GCD) of two numbers (integers) is the largest integer that divides both the numbers. We can find the GCD of two numbers recursively by using the Euclid's algorithm that states

GCD (a, b) = { b, if b divides a , GCD (b, a mod b), otherwise }

GCD can be implemented as a recursive function because if b does not divide a, then we call the same function (GCD) with another set of parameters that are smaller and simpler than the original ones. Here we assume that a > b. However if a < b, then interchange a and b in the formula given above.

Working

Assume a = 62 and b = 8

GCD (62, 8)

rem = 62 % 8= 6

GCD (8, 6)

rem = 8% 6 = 2

GCD (6, 2)

rem = 6% 2 = 0

Return 2

Return 2

Return 2

10. Write a program to calculate GCD using recursive functions.

#include <stdio.h>

int GCD (int, int);

int main()

{

int numl, num2, res;

printf("\n Enter the two numbers: ");

scanf("%d %d", &num1, &num2);

res = GCD (num1, num2);

printf("\n GCD of %d and %d = %d", num1, num2, res);

return 0;

}

int GCD (int x, int y)

int rem;

rem = x%y;

if (rem==0)

return y;

else

return (GCD (y, rem));

}

Finding Exponents

We can find exponent of a number using recursion. To find x^y, the base case would be when y=0, as we know that any number raised to the power 0 is 1. Therefore, the general formula to find x^y can be given as

EXP (x, y) = {1, if y == 0 , x* EXP (X Y-1), otherwise }

Working

exp_rec (2, 4) = 2 * exp_rec ( 2, 3)

exp_rec (2, 3) = 2 * exp_rec (2, 2)

exp_rec (2, 2) = 2 * exp_rec (2, 1)

exp_rec (2, 1) = 2 * exp_rec (2, 0)  

exp_rec (2, 0) = 1

exp_rec (2, 1) = 2 * 1 = 2

exp_rec (2, 2) = 2 * 2 = 4

exp_rec (2, 3) = 2 * 4 = 8

exp_rec (2, 4) = 2 * 8 = 16

11. Write a program to calculate exp (x, y) using recursive functions.

#include <stdio.h>

int exp_rec (int, int);

int main()

{

int num1, num2, res;

printf("\n Enter the two numbers: ");

scanf("%d %d", &numl, &num2);

res = exp_rec (num1, num2);

printf ("\n RESULT = %d", res);

return 0;

}

int exp_rec (int x, int y)

{

if ( y==0)

return 1;

else

return (x * exp_rec ( x, y-1));

}

Fibonacci Series

The Fibonacci series can be given as:

0 1 1 2 3 5 8 13 21 34 55.....

That is, the third term of the series is the sum of the first and second terms. Similarly, fourth term is the sum of second and third terms, and so on. Now we will design a recursive solution to find the nth term of the Fibonacci series. The general formula to do so can be given as:

FIB (n) = {0, if n = 0 & 1, if n = 1, FIB (n-1) + FIB (n-2), otherwise }

As per the formula, FIB (0) = 0 and FIB (1) = 1 and, FIB (2) = FIB (1) +FIB (0) = 1 + 0 = 1. So we have two base cases. This is necessary because every problem is divided into two smaller problems.

12. Write a program to print the Fibonacci series using recursion.

#include <stdio.h>

int Fibonacci (int);

int main()

{

int n, i = 0, res;

printf("Enter the number of terms \n");

scanf("%d", &n);

printf("Fibonacci series\n");

for (i 0; i < n; i++ )

{

res = Fibonacci (i);

printf("%d\t", res);

}

return 0;

}

int Fibonacci (int n)

{

if (n = = 0)

return 0;

else if (n = = 1)

return 1;

else

return ( Fibonacci (n-1) + Fibonacci (n-2) );

}

Output

Enter the number of terms 5

Fibonacci series

0 1 1 2 3