Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied.
A function is recursive if it can call itself; either directly:
void f()
{
f();
}
or indirectly:
void f()
{
g();
}
void g()
{
f();
}
Recursion is just a loop; however, it has one difference from other loops. With recursion, each time a recursive
function is called, a new set of variables is created. This is not true of the other loops
When a function calls itself, a new set of local variables and parameters are allocated storage on the stack, and the
function code is executed from the top with these new variables. A recursive call does not make a new copy of the
function. Only the values being operated upon are new. As each recursive call returns, the old local variables and
parameters are removed from the stack, and execution resumes immediately after the recursive call inside the
function.
The main advantage to recursive functions is that we can use them to create clearer and simpler versions of
several programs.
When writing a recursive function, we should follow these rules:
Recursion rule #1: Every recursive method must have a base case -- a condition under which no
recursive call is made -- to prevent infinite recursion.
When writing recursive functions, we must have a conditional statement, such as an if, somewhere to force the
function to return without the recursive call being executed. If we don't, the function will never return once we
call it. Omitting the conditional statement is a common error when writing recursive functions.
Recursion rule #2: Every recursive method must make progress toward the base case to prevent
infinite recursion. (recursive case)
When writing recursive functions, we must write a recursive case in which there should be a call to same function.
Ex: Suppose we want to calculate the factorial value of an integer. As we know, the factorial of a number is the
product of all the integers between 1 and that number. For example, 4 factorial is 4 * 3 * 2 * 1. This can also be
expressed as 4! = 4 * 3!, where ‘!’ stands for factorial. Thus factorial of a number can be expressed in the form of
itself. Hence this can be programmed using recursion.
Write a program to calculate factorial of a number
/* program to calculate factorial of a number in /* program to calculate factorial of a number
iterative approach*/ using recursion*/
#include<stdio.h> #include<stdio.h>
int main() int fact(int);
{ int main()
int n,fact,i; {
printf("\n Enter any number:"); int n,f;
scanf("%d",&n); printf("\n Enter any number:");
for(i=1,fact=1;i<=n;i++) scanf("%d",&n);
fact=fact*i; f=fact(n);
printf("\n Factorial of %d is %d",n,fact); printf("\n Factorial of %d is %d",n,f);
} }
int fact(int n)
{
int f;
if(n==0||n==1) //base case
return 1;
else
return n*fact(n-1); //recursive case
}
Let us see how the recursion works. Assume n=5. since the value of n is not 1 or 0, the statement will be executed
with n=3. That is,
f=3*fact(2);
will be evaluated. The expression on the right hand side includes the call to fact() with n=4. This call, fact(4), will
return this value: 4*fact(3). Like this, the sequence of operations can be summarized as follows:
f=3*fact(2);
=3*2*fact(1);
=3*2*1
=6
When this recursive program is executed, the recursive function calls are not executed immediately. Rather, these
are placed on a stack until the condition terminates the recursion is encountered. The function calls are then
executed in reverse order, as they are deleted from the stack. Thus, when evaluating a factorial recursively, the
function calls will proceed in the following order:
fact(1)
2*fact(1)
3*fact(2)
The actual values will then be returned in the following order:
fact(1)=1
2*fact(1)=2*1=2
3*fact(2)=3*2=6
/*A program to calculate sum of n natural /*A program to calculate sum of n natural
numbers using iterative approach*/ numbers using recursive approach*/
#include<stdio.h> #include<stdio.h>
int main() int sumNatural(int);
{ int main()
int n,sum,i; {
printf("\n Enter n value:"); int n,s;
scanf("%d",&n); printf("\n Enter n value:");
for(i=1,sum=0;i<=n;i++) scanf("%d",&n);
sum=sum+i; s=sumNatural(n);
printf("\n Sum of %d numbers=%d",n,sum); printf("\n Sum of %d numbers=%d",n,s);
} }
int sumNatural(int n)
{
int sum;
if(n==0)
sum=0; //base case
else
sum=sum+sumNatural(n-1); //recursive case
return sum;
}
/*A program to calculate sum of digits of a /*A program to calculate sum of digits of a
number using iterative approach*/ number using recursive approach*/
#include<stdio.h> #include<stdio.h>
int main() int sumDigits(int);
{ int main()
int num,sum,r; {
printf("\n Enter any number:"); int num,s;
scanf("%d",&num); printf("\n Enter any number:");
sum=0; scanf("%d",&num);
while(num>0) s=sumDigits(num);
{ printf("\n Sum of digits=%d",s);
r=num%10; }
sum=sum+r; int sumDigits(int n)
num=num/10; {
} if(n==0)
printf("\n Sum of digits=%d",sum); return 0;
} else
return (n%10)+sumDigits(n/10);
}
/*A program to evaluate nth fibonacci number in series using recursive approach*/
// Function to calculate the nth Fibonacci number using recursion
#include<stdio.h>
int fib(int x){
if (x ==0)
return 0;
else if(x==1)
return 1;
else
return fib(x - 1) + fib(x - 2);
}
int main(){
int n;
printf("enter n value");
scanf("%d",&n);
int result = fib(n);
printf("%d\n", result);
return 0;
}
OUTPUT::
enter n value7
13
enter n value5
5
enter n value10
55
What is the output of following function for start pointing to first node of following linked list? 1-
>2->3->4->5->6
What does the following function do for a given Linked List with first node as head?