Formula Sheets: Recursion | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

 Page 1


Recursion in Progr amming F ormula Sheet
1. Recursion Basics
• Definition : Function that calls itself to solve smaller instances of the same
problem.
• Components :
– Base Case : Condition to terminate recursion.
– Recursive Case : Function calls itself with modified input.
• Example (F actorial) :
– n! = n×(n-1)! , base case: 0! = 1 .
– Pseudo-code: factorial(n) =
{
1 ifn = 0
n× factorial(n-1) otherwise
.
2. Types of Recursion
• Direct Recursion : Function calls itself directly .
• Indirect Recursion : FunctionA callsB , which cal lsA .
• T ail Recursion : Recursive call is last oper ation, e.g., tail_fact(n,acc) =
{
acc ifn = 0
tail_fact(n-1,n×acc) otherwise
.
• Non-T ail Recursion : A dditional computation after recursive call, e.g., factorial(n) .
• Tree Recursion : Multiple recursive calls, e.g., Fibonacci: fib (n) = fib (n-1)+
fib (n-2) .
3. Recurrence Relations
• Definition : Equation defining function in terms of itself with smaller inputs.
• Examples :
– F actorial: T(n) = T(n-1)+O(1) , base case: T(0) = O(1) .
– Fibonacci: T(n) = T(n-1)+T(n-2)+O(1) , base case: T(0) = T(1) = O(1) .
– Merge Sort: T(n) = 2T(n/2)+O(n) , base case: T(1) = O(1) .
• Solving Methods :
– Recursion Tree : Sum costs at each level.
– Substitution Method : Guess solution, verify b y induction.
– Master Theorem : F orT(n) = aT(n/b)+f(n) :
*
Iff(n) = O(n
log
b
a-?
) , thenT(n) = T(n
log
b
a
) .
*
Iff(n) = T(n
log
b
a
) , thenT(n) = T(n
log
b
a
logn) .
1
Page 2


Recursion in Progr amming F ormula Sheet
1. Recursion Basics
• Definition : Function that calls itself to solve smaller instances of the same
problem.
• Components :
– Base Case : Condition to terminate recursion.
– Recursive Case : Function calls itself with modified input.
• Example (F actorial) :
– n! = n×(n-1)! , base case: 0! = 1 .
– Pseudo-code: factorial(n) =
{
1 ifn = 0
n× factorial(n-1) otherwise
.
2. Types of Recursion
• Direct Recursion : Function calls itself directly .
• Indirect Recursion : FunctionA callsB , which cal lsA .
• T ail Recursion : Recursive call is last oper ation, e.g., tail_fact(n,acc) =
{
acc ifn = 0
tail_fact(n-1,n×acc) otherwise
.
• Non-T ail Recursion : A dditional computation after recursive call, e.g., factorial(n) .
• Tree Recursion : Multiple recursive calls, e.g., Fibonacci: fib (n) = fib (n-1)+
fib (n-2) .
3. Recurrence Relations
• Definition : Equation defining function in terms of itself with smaller inputs.
• Examples :
– F actorial: T(n) = T(n-1)+O(1) , base case: T(0) = O(1) .
– Fibonacci: T(n) = T(n-1)+T(n-2)+O(1) , base case: T(0) = T(1) = O(1) .
– Merge Sort: T(n) = 2T(n/2)+O(n) , base case: T(1) = O(1) .
• Solving Methods :
– Recursion Tree : Sum costs at each level.
– Substitution Method : Guess solution, verify b y induction.
– Master Theorem : F orT(n) = aT(n/b)+f(n) :
*
Iff(n) = O(n
log
b
a-?
) , thenT(n) = T(n
log
b
a
) .
*
Iff(n) = T(n
log
b
a
) , thenT(n) = T(n
log
b
a
logn) .
1
*
Iff(n) = ?(n
log
b
a+?
) , andaf(n/b)= cf(n) forc < 1 , thenT(n) = T(f(n)) .
4. Common Recursive Algorithms
• F actorial : n! = n×(n-1)! , base case: 0! = 1 .
• Fibonacci : fib (n) = fib (n-1)+ fib (n-2) , base c ases: fib (0) = 0 , fib (1) = 1 .
• Binary Search : search(A,l,r,x) = search(A,l,?(l + r)/2?,x) or search(A,?(l +
r)/2?+1,r,x) .
• Tree Tr aversals :
– Preorder: visit(root), preorder(left), preorder(right).
– Inorder: inorder(left), visit(root), inorder(right).
– Postorder: postorder(left), postorder(right), visit(root).
5. T ail Recursion Optimization
• Definition : Compiler optimizes tail-recursive calls to iter ative loops, reusing
stack fr ame.
• Example : T ail-recursive factorial: tail_fact(n,acc) = tail_fact(n-1,n×acc) .
• Benefit : Reduces space complexity fromO(n) toO(1) .
6. Time and Space Complexities
• F actorial :
– Time: O(n) (recurrence: T(n) = T(n-1)+O(1) ).
– Space: O(n) (stack fr ames),O(1) with tail recursion.
• Fibonacci (Naive) :
– Time: O(2
n
) (exponential due to tree recursion).
– Space: O(n) (recursion d epth).
• Binary Search :
– Time: O( logn) (recurrence: T(n) = T(n/2)+O(1) ).
– Space: O( logn) ,O(1) with tail recursion.
• Merge Sort :
– Time: O(n logn) (recurrence: T(n) = 2T(n/2)+O(n) ).
– Space: O(n) (auxiliary ar r a y),O( logn) for stack.
• Tree Tr aversals : TimeO(n) , SpaceO(h) , whereh is tree height.
2