Python Tutorials · Python Functions

Python Recursion

Learn all about Python Recursion in this comprehensive tutorial.

5 min read beginner

•Recursion is when a function calls itself.
•Every recursive function must have two parts:
•The Fibonacci sequence is a classic example where each number is the sum of the two preceding ones.
•Recursion can be used to process lists by handling one element at a time:
•Python has a limit on how deep recursion can go.

Recursion

Recursion is when a function calls itself.

Recursion is a common mathematical and programming concept. It means that a function calls itself. This has the benefit of meaning that you can loop through data to reach a result.

The developer should be very careful with recursion as it can be quite easy to slip into writing a function which never terminates, or one that uses excess amounts of memory or processor power. However, when written correctly recursion can be a very efficient and mathematically-elegant approach to programming.

python

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

Base Case and Recursive Case

Every recursive function must have two parts:

A **base case** - A condition that stops the recursion
A **recursive case** - The function calling itself with a modified argument

Without a base case, the function would call itself forever, causing a stack overflow error.

python

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

Note: The base case is crucial. Always make sure your recursive function has a condition that will eventually be met.

Fibonacci Sequence

The Fibonacci sequence is a classic example where each number is the sum of the two preceding ones. The sequence starts with 0 and 1:

0, 1, 1, 2, 3, 5, 8, 13, ...

The sequence continues indefinitely, with each number being the sum of the two preceding ones.

We can use recursion to find a specific number in the sequence:

python

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

Recursion with Lists

Recursion can be used to process lists by handling one element at a time:

python

def sum_list(numbers):  if len(numbers) == 0:    return 0  else:    return numbers[0] + sum_list(numbers[1:])
my_list = [1, 2, 3, 4, 5]
print(sum_list(my_list))

python

def find_max(numbers):  if len(numbers) == 1:    return numbers[0]  else:    max_of_rest = find_max(numbers[1:])    return numbers[0] if numbers[0] > max_of_rest else max_of_rest
my_list = [3, 7, 2, 9, 1]
print(find_max(my_list))

Recursion Depth Limit

Python has a limit on how deep recursion can go. The default limit is usually around 1000 recursive calls.

python

import sys
print(sys.getrecursionlimit())

If you need deeper recursion, you can increase the limit, but be careful as this can cause crashes:

python

import sys
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())

Note: Increasing the recursion limit should be done with caution. For very deep recursion, consider using iteration instead.

Module quiz

2 questions

Which of the following is true about Python Recursion?

It is strictly typedIt is evaluated at runtimeIt requires explicit memory managementIt is deprecated

What is the most common pitfall when working with Python Recursion?

SyntaxErrorIndentationErrorNameErrorTypeError

Answer all questions to submit.

Python Lambda

Python Generators

Python Recursion

AI Summary

Recursion

Base Case and Recursive Case

Fibonacci Sequence

Recursion with Lists

Recursion Depth Limit

Module quiz