Home/

...

/

Recursion

Recursion

Learn about recursion and see an example of calculating the factorial using recursion.

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 the recursive call to calculate factorial.

    • To calculate 4!, we need 4 * 3!

    • To calculate 3!, we need 3 * 2!.

    • To calculate 2!, we need 2 * 1!.

    • To calculate 1!, we need 1 * 0!.

  • Base case reached: The recursion stops at 0! because we define 0! = 1 ...