Programming Logic
Recursive
Function
(Recursion)
B.Bhuvaneswaran, AP (SG) / CSE
9791519152
bhuvaneswaran@rajalakshmi.edu.in
Introduction
A function which calls itself it is called as recursive function
(recursion).
There are certain problems which are recursive in nature. Such
problems can be solved in fewer steps using a recursive function.
Many mathematical, searching and sorting algorithms can be
simply expressed in terms of a recursive definition.
For example, to compute factorial of a number, a recursive
function can be used.
When the problem is solved through recursion the source code
looks elegant.
Recursive Function (Recursion) Rajalakshmi Engineering College 2
Parts of Recursion
Base condition
• When a function will terminate.
Recursive condition
• The invocation of a recursive call to the function.
Recursive Function (Recursion) Rajalakshmi Engineering College 3
Types of Recursions
Direct recursion
Indirect recursion
Recursive Function (Recursion) Rajalakshmi Engineering College 4
Direct Recursion
In the direct recursion, the same function calls itself from its own
body.
Recursive Function (Recursion) Rajalakshmi Engineering College 5
Indirect Recursion
In indirect recursion the function invokes some other function
which again invokes the function which has invoked it.
That is, it creates a cycle of function calls.
Recursive Function (Recursion) Rajalakshmi Engineering College 6
Example
An useful example of recursion is the evaluation of factorials of a
given number.
The factorial of a number n is expressed as a series of repetitive
multiplications as shown below:
factorial of n = n(n–1)(n–2).........1.
For example:
factorial of 4 = 4 × 3 × 2 × 1 = 24
Recursive Function (Recursion) Rajalakshmi Engineering College 7
Program
int fact(int n)
{
if(n ==0 || n == 1)
return 1;
else
return(n * fact(n - 1));
}
Recursive Function (Recursion) Rajalakshmi Engineering College 8
Explanation
Let us see how the recursion works. Assume n = 5. Since the value of n is not 1,
the statement:
fact = n * factorial(n-l);
will be executed with n = 5. That is,
fact = 5 * factorial(4);
will be evaluated. The expression on the right-hand side includes a call to
factorial with n = 4. This call will return the following value:
4* factorial(3)
Once again, factorial is called with n = 3. That is,
3 * factorial(2);
will be evaluated. The expression on the right-hand side includes a call to
factorial with n = 2. This call will return the following value:
2 * factorial(1);
Once again, factorial is called with n = 1. This time, the function returns 1.
Recursive Function (Recursion) Rajalakshmi Engineering College 9
Explanation
The sequence of operations can be summarized as follows:
fact = 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
=5*4*3*2*1
= 120
Recursive Function (Recursion) Rajalakshmi Engineering College 10
Explanation
Recursive functions can be effectively used to solve problems
where solution is expressed in terms of successively applying the
same solution to subsets of the problem.
When we write recursive functions, we must have an if statement
somewhere to force the function to return without the recursive
call being executed.
Otherwise, the function will never return.
Recursive Function (Recursion) Rajalakshmi Engineering College 11
Recursive evaluation of 5!
Recursive Function (Recursion) Rajalakshmi Engineering College 12
Program
/* Factorial of a number using recursive function - FACTREC.C */
#include <stdio.h>
int fact(int);
int main()
{
int n, f = 1;
printf("Enter a number : ");
scanf("%d", &n);
f = fact(n);
printf("Factorial value of %d is : %d", n, f);
return 0;
}
int fact(int n)
{
if(n ==0 || n == 1)
return 1;
else
return(n * fact(n - 1));
}
Recursive Function (Recursion) Rajalakshmi Engineering College 13
Output
Enter a number : 5
Factorial value of 5 is : 120
Recursive Function (Recursion) Rajalakshmi Engineering College 14
Program
/* Fibonacci series using recursive function - FIBOREC.C */
#include <stdio.h>
int fibo(int);
int main()
{
int n, i;
printf("Enter the number of terms : ");
scanf("%d", &n);
printf("The fibonacci series is :\n") ;
for(i = 0; i < n; i++)
printf("%d\t", fibo(i));
return 0;
}
int fibo(int n)
{
if(n == 0 || n == 1)
return n;
else
return fibo(n - 1) + fibo(n - 2);
Recursive Function (Recursion) Rajalakshmi Engineering College 15
Output
Run 1:
Enter the number of terms : 10
The fibonacci series is :
0 1 1 2 3 5 8 13 21 34
Recursive Function (Recursion) Rajalakshmi Engineering College 16
Program
/* Program to find NCR value of the given numbers - NCR.C */
#include <stdio.h>
long fact(int);
int main()
{
long ncr;
int n, r;
printf("Enter the value for N : ");
scanf("%d", &n);
printf("Enter the value for R : ");
scanf("%d", &r);
if(n >= r)
{
ncr = fact(n) / (fact(n-r) * fact(r));
printf("The NCR value is : %ld", ncr);
}
else
printf("Calculating NCR value is not possible");
return 0;
}
Recursive Function (Recursion) Rajalakshmi Engineering College 17
Program
long fact(int i)
{
long x;
if(i == 0)
return 1;
else
{
x = i * fact(i - 1);
return x;
}
}
Recursive Function (Recursion) Rajalakshmi Engineering College 18
Output
Run 1:
Enter the value for N : 7
Enter the value for R : 5
The NCR value is : 21
Run 2:
Enter the value for N : 5
Enter the value for R : 7
Calculating NCR value is not possible
Recursive Function (Recursion) Rajalakshmi Engineering College 19
Program
/* Program to find the sum of numbers upto n- SONREC.C */
#include <stdio.h>
int funsum(int);
int n;
int main()
{
int sum = 0, res;
printf("Enter the value for n : ");
scanf("%d", &n);
res = funsum(sum);
printf("The sum is : %d", res);
return 0;
}
int funsum(int s)
{
if(s <= n)
return s + funsum(s + 1);
else
return 0;
}
Recursive Function (Recursion) Rajalakshmi Engineering College 20
Output
Run 1:
Enter the value for n : 10
The sum is : 55
Recursive Function (Recursion) Rajalakshmi Engineering College 21
Thank You
