Recursion Flashcards
What is recursion
A function calling itself
Which DS is used to solve recursion
STACK
Every function call has its own?
Stack space and local variables
If no termination condition present in recursive program then what happens
Stack overflow which is a runtime error
For every recursive program, is non recursive program present?
Yes
Time complexity comparison of recursive and non recursive program for same algo
Same
Space complexity comparison of recursive and non recursive program for same algo
Space complexity of recursive program is more
Amount of stack space used by recursive program
Depth of stack
From one call to another call of a recursive prog does code, no. of parameters, name of parameter change?
No only value of parameters can change
Methods for solving recursive problems
Substitution, Recursive tree, Masters theorem
Constant time corresponds to
O(1)
For multiplication by recursion no. of additions for doing m*n
0 if m=0 or n=0
A(m,n-1)+1 if n>0 and m>0
For fibonacci series nth no., no. of additions
0 if n=0 or n=1(n<=1)
fib(n-1)+fib(n-2)+1
Substitution
Substitute until u get a pattern
1+2+3+—–+n
n(n+1)/2
123—–n
n!
Sum of squares of natural nos.
n(n+1)(2n+1)/6
Which log considered in TC
log base 2
(log n)^2
log^2 n
In infinite loop , why is there no stack overflow
Because only one function call
AGP solve method
FInd T(n)
Find 2T(n)
Do T(n)-2T(n)
Find -T(n)
Recursive tree
Find leftmost length, rightmost length and then evaluate upper and lower bounds
Tree height in recursive tree
Stack space is tree height
Decreasing GP value gives
O(1)
Log property a ^ log b c
= c ^ log b a
