Recursion Function 1

1. A function which is called by itself is called recursion

function.
2. In recursive function, whenever a function is called stack memory is used
internally for storing the function return addresses.

3.If the recursion is happening continuously, so that once stack memory is

completely filled with function return addresses, then it leads to
segmentation fault.

Advantage : It reduces code complexity

Disadvantages :
1. Takes more memory in stack.
2. makes slower in execution because of many push & pop operations
 .........
fun
2
#include<stdio.h>
void fun(); void fun()
y Return addr {
int main() //0x1000 int y = 20;
20 0x2004
{ printf("In fun(), y = %d\n",y);
int x = 10; fun();
0x5000 fun }
printf("before fun()\n");
fun(); //0x1004 y
void fun()
Return addr {
printf("after fun()...\n"); int y = 20;
20 0x2004
printf(“x = %d\n”,x); printf("In fun(), y = %d\n",y);
fun();
} 0x4000 fun }
void fun() //0x2000
{ void fun()
y Return addr {
int y = 20;
20 0x1004 int y = 20;
printf("In fun(), y = %d\n",y); printf("In fun(), y = %d\n",y);
fun(); //0x2004 0x3000 fun
fun();
}
}
int main()
x Return addr {
10 0x500
0x1000
int x = 10;
printf("before fun()\n");
0x2000 fun();
main printf("after fun()...\n");
printf(“x = %d\n”,x);
}
_start values

Stack
#include<stdio.h> ........
fun
3
void fun()
void fun(); {
int main() i Return addr
int i = 0;
{ if(i++ < 3) {
0 0x2004 printf("In fun(), i = %d\n",i);
printf("In main()...\n"); fun();
fun(); //0x1003 0x5000 fun }
}void fun()
}
{
void fun() 0x2000 i Return addr int i = 0;
{ 0x2004 if(i++ < 3) {
0
int i = 0; printf("In fun(), i = %d\n",i);
fun();
if(i++ < 3) { 0x4000
fun }
printf("In fun(), i = %d\n",i); }void fun()
fun(); //0x2004 i Return addr
{
int i = 0;
} 0x1003
0 if(i++ < 3) {
} printf("In fun(), i = %d\n",i);
0x3000 fun();
fun }
}
Return addr
int main()
0x500
0x1000 {
printf("In main()...\n");
main fun();
}

_start values

Stack
 1 #include<stdio.h> .......
fun void fun()
4
2 void fun(); {
3 int main() Static int i = 0;
Return addr if(i++ < 3) {
4{ printf("In fun(),i = %d\n",i)
0x2004
5 printf("In main()...\n"); fun();
6 fun(); }
fun }
7} void fun()
8 void fun() {
Return addr Static int i = 0;
9{ if(i++ < 3) {
0x2004
10 static int i = 0; printf("In fun(),i = %d\n",i)
11 if(i++ < 3) { fun();

12 printf("In fun(), i = %d\n",i); fun }

}
13 fun(); void fun()
Return addr {
14 } Static int i = 0;
0x1003
15 } if(i++ < 3) {
printf("In fun(),i = %d\n",i)
fun fun();
i }
}
0 12 34 Return addr
int main()
0x500
0x1000 {
0x1000
printf("In main()...\n");
main fun();
Data }

_start values

Stack
 1 #include<stdio.h>
2 void fun(int);
.....................
fun void fun(int i)
5
3 int main() {
4{ i Return addr
if(i++ < 3) {
5 printf("In main()...\n"); 0x2005
2 3 printf("In fun(), i = %d\n",i)
6 fun(0); // 0x1005 fun(i);
7} 0x5000 }
fun }void fun(int i)
8 void fun(int i)//0 //1 //2 //3
{
9{ i Return addr
10 if(i++ < 3) //0<3 //1<3 //2<3 1 2 0x2005 if(i++ < 3) {
11 { printf("In fun(), i = %d\n",i)
fun(i);
12 printf("In fun(), i = %d\n",i);//1//2//3 0x4000
fun }
13 fun(i); //fun(1); //fun(2); //fun(3) }void fun(int i)
14 } i Return addr
{
15 } 0x1005
0 1 if(i++ < 3) {
printf("In fun(), i = %d\n",i)
0x3000 fun(i);
fun }
}
Return addr
int main()
0x500
0x1000 {
printf("In main()...\n");
main fun(i);
}

_start values

Stack
#include<stdio.h>
void fun(int n);
0
0x6000
.......
fun
pf("\nHello..."); 6
int main()
{ n if(n>0)
Return addr {
printf("In main(),before fun()\n"); 1 0 0x2005 pf("%d ",n);
fun(3); 0x5000 fun(--n);
printf("\nIn main(),after fun()\n"); fun }
pf("\nHello...");
}
void fun(int n) //3 //2 //1 if(n>0)
n Return addr
{
{ 0x2005
2 1 pf("%d ",n);
if(n>0) fun(--n);
0x4000
{ fun }
pf("\nHello...");
printf("%d ",n); //3 //2 //1
fun(--n); //fun(2) //fun(1) //fun(0) if(n>0)
n Return addr {
} 0x1005 pf("%d ",n);
3 2
fun(--n);
printf("\nHello..."); 0x3000 }
fun pf("\nHello...");
}
Return addr
pf("In main(),before fun()\n");
0x500
0x1000 fun(3);
pf("\nIn main(),after fun()\n");
main

_start values

Stack
 1 #include<stdio.h>
2 void fun(int n);
0
0x600
.......
fun pf("\nHello..."); 8
0
3 int main() n if(n>0)
4{ Return addr {
1 0 0x2005 fun(--n);
5 printf("In main(),before fun()\n"); pf("%d ",n);
0x500
6 fun(3); 0 fun
}
pf(“\nHello...”);
7 printf("\nIn main(),after fun()\n"); if(n>0)
8} n Return addr {
9 void fun(int n) //3 //2 //1 2 1 0x2005 fun(--n);
pf("%d ",n);
10 { 0x400 }
11 if(n>0) 0 fun pf(“\nHello...”);
12 { if(n>0)
n Return addr
13 fun(--n); //fun(2) //fun(1) //fun(0) {
3 2 0x1005 fun(--n);
14 printf("%d ",n); //0 //1 //2 pf("%d ",n);
15 } 0x300
fun
}
0 pf(“\nHello...”);
16
17 printf("\nHello..."); Return addr
pf("In main(),before fun()\n");
18 } 0x500
0x1000 fun(3);
pf("\nIn main(),after fun()\n");
mai
n
_start values

Stack
 1 2 3 4
main()
{
n
3
if(n>0)
{
2
fun(--n); 2
n if(n>0)
{ 1
fun(--n); 1
n if(n>0)
{ 0
fun(--n); 0
n if(n>0)
{ 9
fun(--n);
fun(3); pf(n);2 pf(n);1 pf(n); 0 pf(n);
} 2 fun(--n);
1 fun(--n);
0 fun(--n); fun(--n);
1 } 1 0 } 0 -1 } -1 }

7 6 5
1 #include<stdio.h> n if(n>0) n if(n>0) n if(n>0)
2 void fun(int n); { 0 { {
1 fun(--n); 0 fun(--n); -1 fun(--n);
3 int main() pf(n); 0 pf(n); pf(n);
0
4{ fun(--n); fun(--n); fun(--n);
-1 } -1 } }
5 fun(3);
6}
7 void fun(int n) 8
n if(n>0)
8{ {
9 if(n>0) 0 fun(--n);
pf(n);
10 { fun(--n);
11 fun(--n); }
12 printf("%d ",n);
13 fun(--n); 9
14 } n if(n>0)
{
15 } -1 fun(--n);
pf(n);
fun(--n);
}
 1 2 3 4
main()
{
n
3
if(n>0)
{
2
fun(--n); 2
n if(n>0)
{ 1
fun(--n); 1
n if(n>0)
{ 0
fun(--n); 0
n if(n>0)
{ 9
fun(--n);
fun(3); pf(n);2 pf(n);1 pf(n); 0 pf(n);
} 2 fun(--n);
1 fun(--n);
0 fun(--n); fun(--n);
1 } 1 0 } 0 -1 } -1 }

7 6 5
1 #include<stdio.h> n if(n>0) n if(n>0) n if(n>0)
2 void fun(int n); { 0 { {
1 fun(--n); 0 fun(--n); -1 fun(--n);
3 int main() pf(n); 0 pf(n); pf(n);
0
4{ fun(--n); fun(--n); fun(--n);
-1 } -1 } }
5 fun(3);
6}
7 void fun(int n) 8
n if(n>0)
8{ {
9 if(n>0) 0 fun(--n);
pf(n);
10 { fun(--n);
11 fun(--n); }
12 printf("%d ",n);
13 fun(--n); 9
14 } n if(n>0)
{
15 } -1 fun(--n);
pf(n);
fun(--n);
}
 1 #include<stdio.h>
2 int fact(int);
3 int main()
10
4{ n Return addr
5 int n,f; 1 0x2000 return 1;
6 printf("Enter the n value\n"); 0x5000
7 scanf("%d",&n); fact
8
n Return addr
9 f = fact(n); 0x2000
2 return 2*fact(1);
10 printf("f = %d\n",f);
0x4000
11 } fact 1
12 int fact(int n) 2
13 { n Return addr
14 if((n==1)||(n==0)) 3 0x2000 return 3*fact(2);
15 return 1; 0x3000
fact 2
16 else
17 return n*fact(n-1); 6
n f Return addr
18 }
3 6 0x1234
0x1000 f = fact(3);
0x2000 0x2004
main
6

_start values

Stack
//write a program to find factorial of a given number using recursion function.
1 #include<stdio.h>
2 int fact(int,int);
11
3 int main()
4{
5 int n,f;
6 printf("Enter the n value\n");
7 scanf("%d",&n);
8
9 f = fact(n,1);
10 printf("f = %d\n",f);
11 }
12 int fact(int n,int f)
13 {
14 if(n!=0) //4!=0,3!=0,2!=0,1!=0,0!=0
15 {
16 f = f*n; //f=1*4,f=4*3,f=12*2,f=24*1
17 n = n-1; //n=3,n=2,n=1,n=0
18 return fact(n,f);
19 }
20 else
21 return f;
22
23 }
//write a progrm to find the sum of digits using recursion fun.
1 #include<stdio.h>
2 int sum(int n,int s);
12
3 int main()
4{
5 int n;
6 printf("Enter the n value\n");
7 scanf("%d",&n);
8
9 int s = sum(n,0);
10 printf("s = %d\n",s);
11 }
12 int sum(int n,int s)
13 {
14 if(n!=0)
15 {
16 s = s+n%10;
17 n = n/10;
18 return sum(n,s);
19 }
20 else
21 return s;
22 }
//write a program to reverse the string using recurion function.
1 #include<stdio.h>
2 #include<string.h> 13
3 void rev_str(char *,int,int);
4 int main()
5{
6 char s[50];
7 printf("Enter the string\n");
8 scanf("%s",s);
9
10 rev_str(s,0,strlen(s)-1);
11 printf("s = %s\n",s);
12 }
13 void rev_str(char *p,int i,int j)
14 {
15 char temp;
16 if(i<j)
17 {
18 temp = p[i];
19 p[i] = p[j];
20 p[j] = temp;
21 i++, j--;
22 rev_str(p,i,j);
23 }