Recursion

                                                 Recursion 

 A function calling itself is called recursion 

      • There must be a base condition that will terminate the recursion, otherwise it will go into infinite loop.

 Syntax : 

Type fun( param ) {

 if( < base condition > ) {

 1………. 2.

 fun( param ) 

3………. } 

} 

 • Once the functions are executed and the end result is obtained, then it traces back to the previous functions and terminates it until all the calls are closed and terminated. 

• Printing of function can be done on calling time or returning time.

Head Recursion 

#include <stdio.h>
void fun(int n) {
 if(n>0) {
 fun(n-1); 
 printf("%d ",n);
 } 
} 
int main() {
 int x=3;
 fun(x); 
 return 0; 
} 

Output -: 1 2 3

call fun(3)

call fun(2)

call fun(1)

call fun(0)

print 1

print 2

print 3

Tail Recursion 

#include <stdio.h>
void fun(int n) { 
 if(n>0) { 
 printf("%d ",n);
 fun(n-1); 
 }
 }
 int main() { 
 int x=3;
 fun(x); 
 return 0 ;
 }

Output -: 3 2 1

print 3

call fun(2)

print 2

call fun(1)

print 1

call fun(0)

terminate

• Recursion is also just like loop. But the difference is a loop will have only ascending phase or descending, but the recursion will have ascending as well as descending phase.
• Recursive functions are memory consuming.

#include <stdio.h>
void fun(int n) { 
 if(n>0) { 

 printf("%d ",n);
 fun(n-1); 

 printf("%d ",n);
 }
 }
 int main() { 
 int x=3;
 fun(x); 
 return 0 ;
 }

output-:3 2 1 1 2 3

 time complexity O(n) and space complexity O(n)

                1                n=0

T(n) =

                T(n-1)+1   n>0

Solution-:

T(n)=T(n-1)+1 --------------------------------(1)

if put n=n-1

T(n-1)=T(n-1-1)+1

T(n-1)=T(n-2)+1 ------------------------------(2)

put the value of T(n-1) into first equation

T(n)=T(n-2)+1+1

T(n)=T(n-2)+2 --------------------------------(3)

put the value of n=n-1 in the third equation, we got the equation

T(n-1)=T(n-1-2)+2

T(n-1)=T(n-3)+2

put the value of T(n-1) into first equation

T(n)=T(n-3)+2+1

T(n)=T(n-3)+3

:

:

:

:

:

T(n)=T(n-k)+k           Assume that n-k=0  so n=k

n is replaced with k

T(n)=T(n-n)+n

T(n)=T(0) +n

T(n)=n+1    ---------------------O(n)