Mastering Recursion: Classic Examples and How They Simplify Complex Problems

When we encounter problems such as computing factorials or Fibonacci numbers, using ordinary loops can be cumbersome, but recursion makes them much simpler and more efficient. This article shares classic recursion cases, discusses the concept, and deepens understanding of basic recursion usage.

1. Introduction to Recursion

1. Baidu Encyclopedia definition

Recursion (recursion) is the programming technique where a program calls itself.

Recursion is widely used in programming languages. A process or function that directly or indirectly calls itself transforms a large complex problem into smaller, similar problems, allowing the solution to be described with minimal code.

Recursion works by using a finite set of statements to define an infinite set. Generally, recursion requires a base case, a recursive step, and a return step. When the base case is not met, the recursion proceeds; when it is met, the recursion returns.

2. Plain-language understanding

Recursion is when a function calls itself inside its own definition.

3. Everyday analogies for recursion

1. A dictionary: to understand a word you may need to look up other words, and those may require further look‑ups until you reach a definition you fully understand, then you backtrack.

2. Children passing a notebook: a child in row 10 asks the child in row 9 to get the notebook from row 1; each child passes the request further until it reaches row 1, which returns the notebook step by step.

3. An onion: an onion with many layers is like a recursive structure.

4. Simple recursive example

# 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 quotient each time
    if v == 0:
        '''When the quotient is 0, stop and return Done'''
        return 'Done'
    v = recursion(v)  # recursive call
recursion(10)  # function call

Output:

5
2
1
0

5. Characteristics of recursion

From the above we can summarize several key characteristics of recursion:

A clear termination condition must exist.

Each deeper recursive call should reduce the problem size.

Recursion is not highly efficient; too many levels can cause stack overflow because each call adds a stack frame.

Two related terms:

Recurrence : each step builds on the previous one.

Backtracking : after reaching the base case, the function returns values step by step.

2. Classic Recursive Cases

1. Factorial

def factorial(n):
    if n == 1:
        return n  # base case
    n = n * factorial(n-1)  # n! = n * (n-1)!
    return n
print(factorial(5))  # prints 120

2. Fibonacci sequence

# 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... find the 15th number
def fibonacci(n):
    if n <= 2:
        return 1  # first two numbers are 1
    return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(15))  # prints 610

3. Binary search (dichotomy) in a sorted list

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

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

res = dichotomy(0, len(data), data, 222)
print(res)