Search⌘ K
AI Features
Home
Courses
Learn Python 3 Fundamentals

Recursion

Explore recursion by understanding how functions call themselves to solve smaller subproblems. Learn to implement factorial and Fibonacci sequences using recursion, identify base cases, and compare recursive approaches with iteration. Gain practical problem-solving skills and awareness of recursion's benefits and limitations in Python.

We'll cover the following...

Recursion is a programming technique in which a function calls itself. If the problem can be divided into smaller versions, the function can call itself with these smaller subproblems. The concept of dividing a problem into smaller versions of itself is not uncommon, and we have come across it several times in school math, for instance. Let’s take an example.

A factorial of a number N, denoted by N!, is a product of all positive integers less than or equal to N. 4! would be 4 x 3 x 2 x 1.

Can you represent factorial in terms of a smaller version of itself? Can you identify a factorial of a number smaller than 4 in 4 x 3 x 2 x 1.

4! is simply 4 x 3!.

Each recursive call tackles a simpler version of the original problem. This process continues until a base case is reached, which is a simple condition that can be solved directly without further recursion. What do you think is the base case of factorial? Factorial of 1 is 1.

Factorial example

Here's a simple recursive implementation of a factorial function in Python.

Python 3.10.4
def factorial(n):
    if n == 0:  # Base case
        return 1
    else:
        return n * factorial(n - 1)  # Recursive call
result = factorial(4)
print(result)

Explanation

Here’s a step-by-step explanation:

  • Initial call: The process starts with the initial call to calculate 4!.

  • Recursive calls: Here is ...