What is recursion?

In computer science, recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. It involves a function calling itself directly or indirectly. Let's break it down with an example:

Basic Concept of Recursion:

• Self-Referential Function: In recursion, a function solves a problem by calling itself with a smaller or simpler input.
• Base Case: Every recursive function must have a base case, which is a condition that stops the recursion. Without a base case, the function would call itself indefinitely, leading to a stack overflow.
• Recursive Case: This is where the function calls itself with a modified input.

Example: Factorial Calculation

The factorial of a number (n!) is the product of all positive integers up to that number (n). For instance, 5! = 5 × 4 × 3 × 2 × 1 = 120.

Here's how you could implement the factorial function using recursion:

def factorial(n):
    # Base case: factorial of 1 is 1
    if n == 1:
        return 1
    else:
        # Recursive case: n! = n * (n-1)!
        return n * factorial(n - 1)

# Example usage
print(factorial(5))  # Outputs: 120

In this example, factorial is a recursive function. It keeps calling itself with decreasing values of n until it reaches the base case (n == 1). At this point, it stops calling itself and begins to unwind and calculate the factorial.

Understanding Recursion:

1. Stack Behavior: Each time a recursive function calls itself, a new frame is pushed onto the call stack with its own set of variables. Once a base case is reached, the stack begins to unwind, resolving each call.

2. Visualization: Imagine a stack of books. Each recursive call adds a book to the stack. The base case is the last book, after which you stop stacking and start removing (or resolving) from the top.

3. Usage in Algorithms: Recursion is commonly used in sorting algorithms (like quicksort, mergesort), tree and graph traversal (like in depth-first search), and dynamic programming.

Important Considerations:

• Memory Usage: Recursive functions use more memory, as each function call consumes stack space.
• Risk of Stack Overflow: Too many recursive calls can lead to a stack overflow error. This is why ensuring a proper base case is crucial.
• Tail Recursion Optimization: In some languages, tail recursion (where the recursive call is the last operation in the function) can be optimized to avoid increasing the call stack size.

Recursion is a powerful and elegant tool in programming, especially useful in problems that can be broken down into similar subproblems. However, it's important to use it judiciously, keeping in mind its impact on memory and performance.

Ref: Grokking the Art of Recursion for Coding Interviews