top of page

Python Recursion

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller subproblems. Here's an example of a recursive function in Python:

def factorial(n):
    if n == 0 or n == 1:
        return 1
        return n * factorial(n - 1)

In this example, the `factorial()` function calculates the factorial of a given number `n` using recursion. The factorial of a non-negative integer `n` is the product of all positive integers less than or equal to `n`. The base case is when `n` is 0 or 1, where the factorial is defined as 1. Otherwise, the function calls itself with a smaller value `n - 1` and multiplies it by `n`.

Let's see how to use this function:

result = factorial(5)
print(result)  # Output: 120

The `factorial(5)` call returns the factorial of 5, which is 120.

Recursion can be a powerful technique for solving problems that can be divided into smaller, similar subproblems. However, it's important to ensure that a proper base case is defined, so the recursive calls eventually reach a termination condition. Otherwise, it can lead to infinite recursion and stack overflow errors.

Here's another example of a recursive function that calculates the nth Fibonacci number:

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

The `fibonacci()` function calculates the nth Fibonacci number by summing the previous two Fibonacci numbers. The base case is when `n` is 0 or 1, where the function returns `n`. Otherwise, it calls itself recursively with `n - 1` and `n - 2` to calculate the two preceding Fibonacci numbers and adds them together.

Let's use the `fibonacci()` function:

result = fibonacci(6)
print(result)  # Output: 8

The `fibonacci(6)` call returns the 6th Fibonacci number, which is 8.

Recursion can be a powerful tool in programming, but it's important to use it judiciously and ensure that the recursive calls converge towards the base case.

Related Posts

See All

Mastering Lists in Python

Introduction Lists are one of the most fundamental and versatile data structures in Python. They allow you to store and manipulate collections of items, making them an essential tool for any Python pr

Python Anonymous Function

In Python, an anonymous function is a function that is defined without a name. It is also known as a lambda function because it is created using the `lambda` keyword. Anonymous functions are typically


bottom of page