深入理解递归-recursion-mycodeschool

Factorial - a simple recursion

n! :

n*(n-1)! if n>0

 1  if n=0

Recursive function

int Factorial(int n)
{
   if(n==0)
       return 1;
   else
       return n*Factorial(n-1);
}

Fibonacci Sequence -recursion and "gotcha"

F(n):

F(n-1) + F(n-2) if n > 1

n  if n = 0, 1

//Iterative program
int Fib(int n)
{
   if(n<=1)
       return n;
   int F1=0,F2=1,Fn;
   for(int i =2;i<=n;i++)
   {
       Fn = F1 + F2;
       F1 = F2;
       F2 = Fn;
   }
   return Fn;
}
//Recursive program
int Fib(int n)
{
   if(n<=1)
       return n;//base condition: to end the recursion
   else
       return Fib(n-1)+Fib(n-2);
}

in the iterative program, while we are calculating each state or eachvalue of F(i) exactly once

in the recursive implementation, we are calculating it multiple times(recursion tree).

Complexity analysis of recursive programs

Time Complexity

int Factorical(int n){
   if(n==0) return 1;//n==0 cost 1
   else return n*Factorical(n-1)//n* cost 1 n-1 cost 1 in total cost 2
}

T(n) = T(n-1) +3  if n > 0

T(0) = 1

so:

T(n) = T(n-1) +3 = T(n-2) +6 = T(n-3) +9 = ...=T(n-k) + 3K

n - k = 0

k = n

T(n) = T(0) +3n

It takes O(n)

Space Complexity

Maximum depth of the Recursion tree n -- Implicit stack

It takes O(n)

Fibonacci Sequence - Time Complexity analysis

int Fib(int n)
{
   if n <=1 return n;// n <= 1 cost 1
   else return Fib(n-1) + Fib(n-2)// n-1 n-2 + in total cost 3
}

T(0) = T(1) = 1

We assume:T(n-1) = T(n-2)

Lower:

T(n) = 2T(n-2)+C=2(2T(n-4)+C)+C=2^k T(n-2k)+(2^k-1)C

n-2k=0

k=n/2

T(n) = 2^n/2 T(0) +(2^n/2 - 1)C = (1+C)2^n/2-C

Upper:

T(n)=2T(n-1) +C=2(2T(n-2)+C)+C=2^kT(n-k)+(2^k-1)C

n-k=0

k=n

T(n) = 2ⁿT(0)+(2^n-1-1)C=(1+C)2ⁿ-C

Lower bound : T(n) 2^n/2

Upper bound : T(n) 2ⁿ

O(2ⁿ) -> Fib(ercursion) exponential time algorithm

O(n) -> Fib(Iterative) linear time algorithm

Recursion with memorization

We are avoiding all the re-calculation of the same state

#include<iostream>
#define MAXFIB
using namespce std;

int F[MAXFIB];

int Fib(int n)
{
   if(F[n] != -1) return F[n];
   F[n] = Fib(n-1)+Fib(n-2);
   return F[n];
}

int main(void)
{
   for(int i =0;i<51;i++)
   {
       F[i]=-1;
   }
   F[0]=0;
   F[1]=1;
   int n;
   cout<<"please input a number of Fib"<<endl;
   cin>>n;
   int result = Fib(n);
   cout<<result;
   return;
}

Fibonacci Sequence -Space Complexity analysis

consumed by a recursive program is proportional to the maximum depth of this recursion tree

O(n)

Calculate xⁿ - using recursion

recursion one:

xⁿ =

x*x^n-1  if n > 0

1  if n = 0

recursion two:

xⁿ =

x^n/2 * x^n/2 if n is even

x*x^n-1 if n is odd

1  if n = 0

//recursion one
Pow(x,n)
{
   if(n==0) return 1; //n==0 cost1
   else return x*Pow(x,n-1);//x* and n-1 in total cost 2
}
//recursion two
Pow(x,n)
{
   if(n==0) return 1;
   else if(n%2==0)
   {
       int y = Pow(x,n/2);
       return y*y;  //return  Pow(x,n/2)*Pow(x,n/2) is not good, it lead to once new recursion
   }
   else return x*Pow(x,n-1);
}

recursion one O(n)

T(n) = T(n-1) + C ,n>0

T(0) = 1

T(n)=T(n-1)+C=T(n-2)+2C=T(n-k)+kC

n-k=0

k=0

T(n)=T(0)+nC

T(n)=nC+1

recursion two O(log_n)

T(n) = T(n/2)+C1,if n is even

 T(n-1)+C2,if n is odd

T(0)=1,T(1)=1+C2

T(n)=T(n/2)+C=T(n/4)+2C=T(n/8)+3C=T(n/2^k)+kC

n/2^k =1

k=log₂ n

T(n) =1+C2+Clog₂ n

Modular Exponentiation - using recursion

xⁿ mod M eg: 5³ % 7 = 125%7 = 6

(a*b)%M =((a%M)*(b%M))%M

int Mod(int x,int n,int m)
{
   if(n==0) return 1;
   else if(n%2==1)
   {
       int y=Mod(x,n/2,m);
       return (y*y)%m;
   }
   else return ((x%m)*Mod(x,n-1,m))%m;
}