Recursive Function

A recursive function is a function that calls itself in order to solve a problem.

• It breaks down a complex problem into smaller instances of the same problem, and continues calling itself with these smaller instances until a base condition is met.

Why Use Recursion?

• Useful for problems that can be broken into similar subproblems (e.g., factorial, Fibonacci, tree traversals).
• Makes code shorter and more elegant for divide-and-conquer algorithms.
• Mimics mathematical definitions (like n! = n × (n-1)!).

Important Notes on Recursion:

• Every recursive function must have a base case to stop calling itself.
• Recursive functions can lead to stack overflow if the recursion depth is too high.
• Some problems are better solved with loops for efficiency.

Example – Factorial Using Recursion:

def factorial(n):
    if n = = 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # Output: 120

Explanation:

• factorial(5) calls factorial(4)
• factorial(4) calls factorial(3)
• This continues until factorial(0) returns 1
• Then each call returns back up the chain:
  1 × 1 = 1 → 2 × 1 = 2 → 3 × 2 = 6 → 4 × 6 = 24 → 5 × 24 = 120

Another Example – Fibonacci Series:

def fibonacci(n):
    if n < = 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(6))  # Output: 8

Explanation:

• Calculates the 6th Fibonacci number.
• Uses recursive calls to build the sequence: 0, 1, 1, 2, 3, 5, 8