Python Recursion Overview

Vincent Yuan · updated on Aug 22, 2023 · 2 min read

Tech Python

1 Introduction to Recursion

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller instances of the same problem. Recursion is particularly useful for solving problems that can be divided into smaller, similar subproblems. It's a common concept in programming and is often used in algorithms, data structures, and mathematical computations.

Here's a simple explanation of recursion using Python, along with some examples:

2 Basic Structure of a Recursive Function

A recursive function consists of two parts:

Base Case: A condition that specifies when the recursion should stop. It's the simplest version of the problem that doesn't require further recursion.
Recursive Case: A call to the function itself with modified arguments, bringing the problem closer to the base case.

3 Examples

Example 1: Factorial Calculation:

Factorial of a non-negative integer n (denoted as n!) is the product of all positive integers from 1 to n.

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

result = factorial(5)
print(result)

The output is:

120 (5! = 5 * 4 * 3 * 2 * 1)

Example 2: Fibonacci Sequence:

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

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

result = fibonacci(7)
print(result)

The output is:

13 (Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, ...)

Example 3: Countdown:

A simple example of recursion that prints a countdown.

def countdown(n):
    if n <= 0:
        print("Blastoff!")
    else:
        print(n)
        countdown(n - 1)

countdown(5)

The output is:

5
4
3
2
1
Blastoff!

Conclusion

Recursion can be a powerful technique, but it's essential to design the base case and the recursive case carefully to ensure that the function terminates correctly. Additionally, excessive recursion can lead to high memory usage and slow performance, so some problems can be solved more efficiently using iterative approaches.

In fact, a series of traversal functions used to build a decision tree by hand have applied recursion, check out this real use case: