Function recursion in C programming

Calling of same function from its function body is known as function recursion. It is alternative of loop. Any c program which is possible using loop it must be possible using function recursion. Simple example:

Find the sum of all even numbers from 0 to 20 using function recursion. Program:

int main(){
int total;
total=sum(2);
printf("%d",total);
return 0;
}
int sum(int i){
static int even=0;
if(i<=20){
even=even+i;
sum(i+2); //calling same function
}
return even;
}

Output:
It is very difficult to understand the execution as well as to write the function recursion program.

How to write function recursion program in easier way:

I have already told it is very difficult to write function recursion program directly. If any person is writing such program directly he may be memorized that program. I am telling a very nice trick: how to write function recursion program in easier way? As we know any c program which possible using loop it must be possible using function recursion.

Steps for how to write a function recursion program:

Step1: First of all write same program using while loop and function. (Except main function)
Step 2: In that function make all local variable static.
Step 3: Replace while keyword by if.
Step 4: The increment or decrement of variable which is used for condition checking, replace with function call and pass the parameter of that incremented or decremented variable. Now understand by example:

Find the sum of all even numbers from 0 to 20 using function recursion.

Step 1: Write the same program using while loop and function. Here function is sum.

int main(){
int total;
total=sum(2);
printf("%d",total);
return 0;
}
int sum(int i){
int even=0;
while(i<=20){
even=even+i;
i=i+2;
}
return even;
}

Step 2: Make local variable even as static variable

int sum(int i){
static int even=0;
while(i<=20){
even=even+i;
i=i+2;
}
return even;
}

Step 3: Replace while keyword by if keyword.

int sum(int i){
int even=0;
if(i<=20){
even=even+i;
i=i+2;
}
return even;
}

Step 4: Since here variable i has used in condition checking. So replace the statement i=i+2 by sum (i+2).

int sum(int i){
int even=0;
if(i<=20){
even=even+i;
sum(i+2);
}
return even;
}

Following only three simple change you can write any difficult function recursion program.

int main(){
int total;
total=sum(2);
printf("%d",total);
return 0;
}
int sum(int i){
int even=0;
if(i<=20){
even=even+i;
sum(i+2);
}
return even;
}

One more example:

Write a program to find a factorial of given number using function recursion.

Step 1: write same program using while loop and function.

int main(){
int fact,num;
scanf("%d",&num);
fact=factorial(num);
printf("%d",fact);
return 0;
}
int factorial(int num){
int fact=1; //make it static
while(num>0){ //replace while by if
fact=fact*num;
num--; // replace by function call as factorial(num-1);
}
return fact;
}

After following step1, step 2, step 3:
int main(){
int fact,num;
scanf("%d",&num);
fact=factorial(num);
printf("%d",fact);
return 0;
}
int factorial(int num){
static int fact=1;
if(num>0){
fact=fact*num;
factorial (num-1);
}
return fact;
}

Note1: In step 3 while calling function don’t pass the parameter using unary operator like factorial (num--);

Note2: write the function in such a way parameter of calling function must be used in conditional statement. For example in the above program:

int factorial(int num)

num is function parameter and num is also used in the conditional if statement.

7 comments:

sourabh mukherjee said...

very very informative and concept clearing way

Anonymous said...

very useful ! now i am comfortable with recursion

Einstein's Descendents said...

can you do the same for PERFECT NUMBERS???

Einstein's Descendents said...

#include
#include

void main()
{
int perfect(int n);
int x,n,y,m;
clrscr();
printf("Enter a number: ");
scanf("%d", &n);
x=perfect(sum);
if(x==n)
printf("%d is the perfect number", x);
else
printf("It is not perfect");
getch();
}
int perfect(int n)
{
static int sum=0;
static int i=2;
if(i<=n)
{
if(n%i==0)
{
sum=sum+(n/i);
}
i++;
perfect(sum);
}
return sum;
}

//but their seems to be some error..LOGICAL..

sumit setia said...

@Einstein:u r calling the function perfect by sending the value of sum because of that ur number is changing when (n%i==0).. so call function by sending n..
/* check out the number is perfect or not */
#include
#include
int perfect(int);
int main()
{
int n,x;
printf("Enter a number");
scanf("%d",&n);
x=perfect(n);
if(x==n)
printf("\n%d is a perfect number",x);
else
printf(" Not a perfect number");
getch();
return 0;
}
int perfect(int n)
{
static int i=2,sum=0;
int j;
if(i<=n)
{
j=n%i;
if(j==0)
{
sum=sum+(n/i);


}
i++;
perfect(n);

}
return(sum);
}



Doudou Dao said...

NICE

srinivas gummadi said...

recursion in local variable program and global variabe