Master Recursion: Classic Python Examples and Core Concepts

When encountering problems like computing a factorial or generating the Fibonacci sequence, using ordinary loops can be cumbersome, whereas recursion often provides a simpler and more elegant solution. This article shares classic recursion cases, personal insights, and aims to deepen understanding of recursion fundamentals.

1. Recursion Overview

1.1 Definition (Baidu Baike)

Recursion is a programming technique where a program calls itself.

As an algorithm, recursion is widely used in programming languages. A function that directly or indirectly calls itself transforms a large, complex problem into smaller, similar sub‑problems, allowing the solution to be expressed with minimal code.

Recursion works by defining an infinite set with a finite number of statements. Generally, recursion requires a base case, a recursive step, and a return step. When the base condition is not met, the function proceeds with the recursive step; when it is met, it returns.

1.2 Plain Explanation

Recursion occurs when a function calls itself within its own body.

1.3 Everyday Analogies

1. A dictionary is recursive: looking up a word may lead to other words, and this process continues until a definition is fully understood, then you backtrack.

2. A child in the 10th row passes a request to the 9th row, and so on, until it reaches the 1st row; the book is then passed back forward, illustrating function calls and the call stack.

3. An onion with multiple layers.

1.4 Simple Recursive Example

<code># Divide 10 by 2 repeatedly until the quotient is 0, printing each quotient.
def recursion(n):
    v = n // 2  # floor division, keep integer
    print(v)    # output the current quotient
    if v == 0:
        '''When the quotient is 0, stop and return Done'''
        return 'Done'
    v = recursion(v)  # recursive call
recursion(10)  # initial call
</code>

Output:

<code>5
2
1
0
</code>

1.5 Characteristics of Recursion

From the discussion above, recursion has the following traits:

A clear termination (base) condition.

Each deeper recursive call should operate on a smaller problem size.

Recursion can be inefficient; excessive depth may cause stack overflow because each call adds a stack frame.

Two related terms:

Recursion vs. Iteration : Each recursive step builds on the previous one, similar to iteration.

Backtracking : When the termination condition is reached, the function returns step by step, unwinding the call stack.

2. Classic Recursive Cases

2.1 Factorial

<code># Compute n! recursively

def factorial(n):
    if n == 1:
        return n  # base case
    n = n * factorial(n-1)  # recursive step
    return n

res = factorial(5)
print(res)  # prints 120
</code>

2.2 Fibonacci Sequence

<code># Return the nth Fibonacci number

def fibonacci(n):
    if n <= 2:
        return 1  # first two numbers are 1
    v = fibonacci(n-1) + fibonacci(n-2)
    return v

print(fibonacci(15))  # prints 610
</code>

2.3 Binary Search in a Sorted List

<code>data = [1,3,6,13,56,123,345,1024,3223,6688]

def dichotomy(min_idx, max_idx, d, target):
    mid = (min_idx + max_idx) // 2
    if mid == 0:
        return 'None'
    if d[mid] < target:
        print('Search right')
        return dichotomy(mid, max_idx, d, target)
    elif d[mid] > target:
        print('Search left')
        return dichotomy(min_idx, mid, d, target)
    else:
        print('Found %s' % d[mid])
        return d[mid]

res = dichotomy(0, len(data), data, 222)
print(res)
</code>

These examples illustrate how recursion can replace iterative loops for problems that naturally decompose into smaller, similar sub‑problems.