Recursion Concepts in Programming

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem until it reaches a base case.

Key Concepts of Recursion

• Base Case (Termination Condition): The simplest instance of the problem which can be solved directly, stopping further recursive calls.
• Recursive Case: The part where the function calls itself to work on smaller subproblems.
• Termination: Every recursive function must ensure it approaches the base case and terminates to avoid infinite recursion.
• Call Stack: Each recursive call adds a stack frame that holds state until the base case is reached and the calls start returning.

Example 1: Factorial Calculation

Factorial of a number n (written as n!) is the product of all positive integers up to n.

def factorial(n):
    if n == 0 or n == 1:  # Base case
        return 1
    else:
        return n * factorial(n - 1)  # Recursive case

print(factorial(5))  # Output: 120

Example 2: Fibonacci Sequence

The Fibonacci sequence is defined such that each number is the sum of the two preceding ones, starting from 0 and 1.

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

print(fibonacci(7))  # Output: 13

How to Understand Recursion?

• Each recursive call solves a smaller part of the problem.
• When the base case is hit, the function returns and the calls unravel in reverse order.
• Recursion can be visualized as a sequence of function calls stacked on top of each other.

Advantages and Disadvantages of Recursion

• Advantages: Simplifies code, makes some complex problems easier to solve, and is elegant.
• Disadvantages: Can cause stack overflow if base case is missing or for very deep recursion; sometimes less efficient due to function call overhead.