Recursion (Copy)

Introduction to Recursion

• Definition:
  • Recursion is a computational process where a function or procedure calls itself.
  • It is defined using:
    • A base case – a condition where the recursion stops.
    • A general case – the recursive step that reduces the problem towards the base case.
• Example – Factorial Calculation:
  • Factorial of a number (n!) is defined as:
    • Base case: 0! = 1
    • Recursive case: n! = n × (n – 1)!
  • This recursive definition allows computing factorial values using function calls.

Key Terminologies in Recursion

• Base Case:
  • The simplest case in recursion that does not require further function calls.
• General Case:
  • The recursive formula applied to break down a complex problem.
• Winding:
  • The process where recursive calls continue until the base case is reached.
• Unwinding:
  • The process of returning values back through recursive calls after reaching the base case.

Recursive Factorial Program Examples

• Python Implementation:

  def factorial(number):
      if number == 0:
          return 1
      else:
          return number * factorial(number - 1)
  
  print(factorial(0))  # Output: 1
  print(factorial(5))  # Output: 120
  

• Pseudocode Representation:

  FUNCTION factorial(number: INTEGER) RETURNS INTEGER
      IF number = 0 THEN
          RETURN 1
      ELSE
          RETURN number * factorial(number - 1)
  ENDFUNCTION
  

• Trace Table for factorial(3):
  • Function calls occur in sequence until the base case is met.
  • The values then return in reverse order (unwinding).

Other Examples of Recursion

Fibonacci Series

• Definition: Each term is the sum of the two preceding terms.
• Formula:
  • Base cases: F(0) = 0, F(1) = 1
  • Recursive case: F(n) = F(n-1) + F(n-2)
• Pseudocode Representation:

  FUNCTION fibonacci(n: INTEGER) RETURNS INTEGER
      IF n = 0 THEN
          RETURN 0
      ELSE IF n = 1 THEN
          RETURN 1
      ELSE
          RETURN fibonacci(n-1) + fibonacci(n-2)
  ENDFUNCTION
  

Compound Interest Calculation Using Recursion

• Definition:
  • Principal amount grows with compound interest over time.
• Formula:
  • Base case: When years = 0, total amount = principal.
  • Recursive case: totaln = total(n-1) * rate
• Pseudocode Implementation:

  FUNCTION compoundInt(principal, rate, years: REAL) RETURNS REAL
      IF years = 0 THEN
          RETURN principal
      ELSE
          RETURN compoundInt(principal * rate, rate, years - 1)
  ENDFUNCTION
  

• Example Calculation for Principal = 100, Rate = 1.05, Years = 3:
  • Call Sequence:
    • compoundInt(100, 1.05, 3) → compoundInt(105, 1.05, 2)
    • compoundInt(105, 1.05, 2) → compoundInt(105, 1.05, 1)
    • compoundInt(105, 1.05, 1) → compoundInt(105, 1.05, 0)
  • Unwinding Results:
    • compoundInt(105, 1.05, 0) → 100
    • compoundInt(105, 1.05, 1) → 105
    • compoundInt(105, 1.05, 2) → 110.25
    • compoundInt(105, 1.05, 3) → 115.76

Benefits of Recursion

• Conciseness:
  • Recursive solutions often require fewer lines of code than iterative approaches.
• Problem-Solving Simplicity:
  • Easier to define solutions for complex problems.
• Natural Fit for Problems:
  • Certain problems (e.g., tree traversal, Fibonacci series) are naturally recursive.

Drawbacks of Recursion

• Performance Concerns:
  • Excessive recursive calls increase memory usage.
  • Heavy stack usage can lead to stack overflow.
• Efficiency Issues:
  • Fibonacci recursion has exponential complexity O(2^N).
  • Iterative solutions are often more efficient.

How a Compiler Implements Recursion

• Use of Stack for Function Calls:
  • Each recursive function call stores:
    • Return address.
    • Local variables.
  • The stack grows during winding and shrinks during unwinding.
• Risk of Stack Overflow:
  • Example: factorial(100) requires 100 stack frames before returning results.