Unit 6: Recursion  (DSA)– Exam Revision Notes

1. Introduction to Recursion

• Recursion = Process in which a function calls itself to solve a smaller instance of a problem.
  
• Base case and recursive case are essential to prevent infinite recursion.
  
• Often used in mathematical computations, algorithms, and data structures.
  

2. Principle of Recursion

1. Base Case – Condition where recursion stops.
   
2. Recursive Case – Part of function that calls itself with smaller input.
   
3. Stack Usage – Each recursive call stored on call stack until base case is reached.
   

3. Recursion vs Iteration

4. Common Recursion Examples

1. Tower of Hanoi (TOH)
   
   • Move n disks from source to destination using auxiliary rod.
     

Recursive formula:

Move n-1 disks from source to auxiliary

Move nth disk to destination

Move n-1 disks from auxiliary to destination

2. Fibonacci Series
   
   • nth term = sum of (n-1)th and (n-2)th terms.
     
   • Recursive function calls for fib(n-1) and fib(n-2).
     

5. Applications of Recursion

1. Tree Traversal – Preorder, Inorder, Postorder.
   
2. Graph Traversal – DFS uses recursion implicitly.
   
3. Divide and Conquer Algorithms – Merge sort, Quick sort.
   
4. Mathematical Problems – Factorial, Fibonacci, GCD.
   
5. Backtracking Problems – N-Queens, Maze solving.
   

6. Advantages of Recursion

• Simplifies code for complex problems.
  
• Natural fit for divide and conquer algorithms.
  
• Useful in dynamic data structures like trees and graphs.
  

7. Disadvantages of Recursion

• Higher memory usage due to call stack.
  
• Slower execution for large input sizes.
  
• Risk of stack overflow if base case is not reached.
  

Key Takeaways – Unit 6

• Recursion = solving problem by self-calling function.
  
• Requires base case and recursive case.
  
• Advantages: simple, elegant, natural for tree/graph problems.
  
• Disadvantages: stack overhead, slower, risk of stack overflow.
• Widely used in TOH, Fibonacci, tree traversal, divide & conquer algorithms.