kioku-space
Posts Tags Categories Series About
kioku-space

Contents

Contents

Python Interactive Guide - Step 3 Functions (6) - Recursive Functions

 included in  category Guides and series Python Interactive Guide
     1525 words   7 minutes 
Series - Python Interactive Guide
Info
  • This course, Python Interactive Guide, is designed to help you learn the basics of Python programming through hands-on, interactive examples.
  • The “Style Guide” sections introduce clean coding practices, mainly based on PEP8.
  • You can run and experiment with every code example.
    Feel free to try things out - reloading the page will reset everything.

This is a continuation of “Step 3 Functions.”

Let’s start by looking at the following code:

In this program, the function calls itself (factorial) from within its definition.
This mechanism where a function calls itself is called recursion, and functions that use recursion are called recursive functions.

To understand how recursive functions work, it’s helpful to trace the factorial calculation step by step.
When we call factorial(5), the following steps happen in sequence:

  1. Execute factorial(5)
    • Need to return 5 * factorial(4), but first need the result of factorial(4)
  2. Execute factorial(4)
    • Need to return 4 * factorial(3), but first need the result of factorial(3)
  3. Execute factorial(3)
    • Need to return 3 * factorial(2), but first need the result of factorial(2)
  4. Execute factorial(2)
    • Need to return 2 * factorial(1), but first need the result of factorial(1)
  5. Execute factorial(1)
    • Since n <= 1, return 1
  6. Resume factorial(2) processing, return 2 * 1 = 2
  7. Resume factorial(3) processing, return 3 * 2 = 6
  8. Resume factorial(4) processing, return 4 * 6 = 24
  9. Resume factorial(5) processing, return 5 * 24 = 120 as the final result

The following code lets us see what’s happening at each step:

When creating a recursive function, two key elements are needed:

Elements of Recursive Functions
  1. Base Case: The condition where recursion ends
    • In the example above, when n <= 1, it returns 1 without further recursion
  2. Recursive Step: Breaking the problem into smaller parts and calling itself
    • In the example above, n * factorial(n - 1) breaks it into smaller problems

Recursive functions are particularly effective when a problem can be broken down into smaller problems of the same form.
Let’s look at some classic examples.

The Fibonacci sequence is a series where each number is the sum of the two preceding ones:

  • 0th number: 0
  • 1st number: 1
  • nth number: n-1th number + n-2th number (for n >= 2)

This sequence can be naturally expressed as a recursive function:

Recursive functions are also effective when dealing with hierarchical structures.
Here’s an example that visually outputs an organizational structure in a tree format:

📚Exercise

Create a recursive function flatten to flatten nested lists
(e.g., flatten([1, [2, [3, 4], 5]) = [1, 2, 3, 4, 5])

Example Solution
📚Exercise

Create a recursive function collatz that returns the number of steps needed for a positive integer n to reach 1 following these rules:

  • If n is 1: end the process
  • If n is even: divide n by 2
  • If n is odd: multiply n by 3 and add 1

(For example: with n=6, the sequence is 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1, so collatz(6) = 8)

Example Solution

The fibonacci function we used earlier becomes extremely inefficient as n increases exponentially:

To solve this problem, we can use a technique called memoization. Memoization stores the results of expensive function calls and reuses them when the same inputs occur again.

For example, when calculating fibonacci(5):

  1. Calculate fibonacci(4) + fibonacci(3)
  2. To calculate fibonacci(4), we need fibonacci(3) + fibonacci(2)
  3. To calculate fibonacci(3), we need fibonacci(2) + fibonacci(1)

As you can see, calculations for the same arguments (like fibonacci(3)) happen multiple times.
With memoization, we can avoid these redundant calculations and get results more efficiently.

Python has a feature called decorators that can modify functions. The cache decorator from the functools module makes it easy to memoize functions (decorators will be explained in more detail later):

Notes on Memoization
  • Memoization is effective for functions that always return the same output for the same input.
    For functions whose output depends on factors other than their input (e.g., a function returning the current time), memoization may cause unintended behavior.
  • Memoization consumes memory, so you need to consider the trade-off between memory usage and processing speed.
  • When using the cache decorator from functools, function arguments must be immutable (hashable).
Column: Computational Complexity of Fibonacci Sequence

There’s a significant difference in computational complexity between simple recursive implementation and memoized implementation of the Fibonacci sequence.

Simple recursive implementation of the Fibonacci sequence has a time complexity of O(2^n).
This is because each call generates two recursive calls, and the same values are recalculated multiple times.

For example, when calculating fibonacci(5):

  • fibonacci(5) calculates fibonacci(4) and fibonacci(3)
  • fibonacci(4) calculates fibonacci(3) and fibonacci(2)
  • fibonacci(3) calculates fibonacci(2) and fibonacci(1)

As you can see, values like fibonacci(3) and fibonacci(2) are calculated multiple times, causing the number of calculations to grow exponentially.

graph TD
    F5["fibonacci(5)"]
    F54["fibonacci(4)"]
    F543["fibonacci(3)"]
    F5432["fibonacci(2)"]
    F5431["fibonacci(1)"]
    F54321["fibonacci(1)"]
    F54320["fibonacci(0)"]
    F542["fibonacci(2)"]
    F5421["fibonacci(1)"]
    F5420["fibonacci(0)"]
    F53["fibonacci(3)"]
    F532["fibonacci(2)"]
    F5321["fibonacci(1)"]
    F5320["fibonacci(0)"]
    F531["fibonacci(1)"]

    F5 --> F54
    F5 --> F53

    F54 --> F543
    F54 --> F542

    F543 --> F5432
    F543 --> F5431

    F5432 --> F54321
    F5432 --> F54320

    F542 --> F5421
    F542 --> F5420

    F53 --> F532
    F53 --> F531

    F532 --> F5321
    F532 --> F5320

With memoization, the time complexity improves dramatically to O(n).

For example, when calculating fibonacci(5), we need values from fibonacci(4) to fibonacci(0) multiple times, but with memoization, each value only needs to be calculated once, effectively requiring just 5 calculations.

graph TD
    F5["fibonacci(5)"]
    F54["fibonacci(4)"]
    F543["fibonacci(3)"]
    F5432["fibonacci(2)"]
    F5431["fibonacci(1)"]
    F54321["fibonacci(1)"]
    F54320["fibonacci(0)"]
    F542["fibonacci(2)"]
    F5421["fibonacci(1)"]
    F5420["fibonacci(0)"]
    F53["fibonacci(3)"]
    F532["fibonacci(2)"]
    F5321["fibonacci(1)"]
    F5320["fibonacci(0)"]
    F531["fibonacci(1)"]

    F5 --> F54
    F5 --> F53

    F54 -. Retrieved from memo .-> F543
    F54 -. Retrieved from memo .-> F542

    F543 -.-> F5432
    F543 -.-> F5431

    F5432 -.-> F54321
    F5432 -.-> F54320

    F542 -.-> F5421
    F542 -.-> F5420

    F53 --> F532
    F53 --> F531

    F532 -. Retrieved from memo .-> F5321
    F532 --> F5320

    %% Memoized nodes have gray border, gray background, semi-transparent
    style F543 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
    style F542 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
    style F5321 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
    style F5432 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
    style F5431 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
    style F54321 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
    style F54320 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
    style F5421 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
    style F5420 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3

Below is a benchmark comparison between simple recursive implementation and memoized implementation using a benchmarking library:

The benchmark results clearly show that computational complexity increases exponentially without memoization, while memoized implementation runs efficiently.

Every time a recursive function is called, information needed for execution (local variables, arguments, return address, etc.) is stacked in memory as a “stack frame”.
Since stack space is limited, there’s a limit to recursion depth.

What is a Stack Frame?

When a function is called, the computer allocates a memory region called a “stack frame”.
This frame stores information needed to execute the function (local variables, arguments, return address, etc.).

In recursive functions, stack frames are handled as follows:

  1. Each time a function calls itself, a new stack frame is added to the stack
  2. When a function completes, its stack frame is removed (freed)
  3. In deep recursion, many frames exist simultaneously temporarily
graph TD
    A["factorial(5) 
 n=5"] --> B["factorial(4) 
 n=4"]
    B --> C["factorial(3) 
 n=3"]
    C --> D["factorial(2) 
 n=2"]
    D --> E["factorial(1) 
 n=1"]

The diagram above shows the stack frames formed during recursive calls to the factorial function.

When the maximum recursion depth is reached, Python raises a RecursionError:

In Python, the recursion depth limit varies by platform (OS and Python implementation), but it’s typically set around 1000. You can check it with this code:

This limit can be changed using sys.setrecursionlimit(), but setting it too high risks running out of memory and causing a stack overflow error:

Notes on Changing Recursion Depth
  • Increasing the recursion depth limit is only a temporary solution
  • For a fundamental solution, review your algorithm (replace with iterative processing or implement memoization)
  • Excessively deep recursion not only risks stack overflow but also reduces processing efficiency

Most processes that can be expressed with recursion can also be expressed with loops (iterative processing).
For example, factorial calculation can be done with a loop like this:

When deciding between recursion and loops, consider these points:

  1. Readability: For some problems, recursive expressions may be more natural and easier to understand
  2. Efficiency: Generally, loops use less memory and are more efficient
  3. Limitations: Recursion has depth limits, so it may reach limits with large inputs
📚Exercise

The collatz function we dealt with in the previous practice problem uses recursion, which has a maximum depth limitation.
Rewrite the collatz function using a while loop to make it work for any integer.

Example Solution

In this section, we learned the following key points about recursive functions:

  1. Concept of Recursive Functions: A mechanism where a function calls itself
  2. Base Case and Recursive Step: Two essential elements for correctly functioning recursive functions
  3. Examples of Recursion: Factorial, Fibonacci sequence, hierarchical structure traversal, etc.
  4. Memoization: An important technique to optimize recursive calculations
  5. Recursion Depth: There are depth limits to recursion based on the execution environment
  6. Recursion vs. Loops: Comparing their strengths, weaknesses, and when to use each

Recursion is a powerful technique that can express complex processes simply.
However, it’s important to understand its mechanisms and limitations to avoid pitfalls like infinite recursion and stack overflow.

Related Content

Python Interactive Guide - Step 3 Functions (5) - Scope

Python Interactive Guide - Step 3 Functions (4) - Parameter Assignment (Pass by Assignment)

Python Interactive Guide - Step 3 Functions (3) - Special Parameters

Python Interactive Guide - Step 3 Functions (1) - Function Basics (2)

Python Interactive Guide - Step 3 Functions (1) - Function Basics (1)

Updated on 2025-08-09
 Python
 | Home