Python Recursive Functions

Python recursive functions are functions that call themselves to solve a problem in smaller steps. Recursion is a powerful technique used to solve problems where a solution can be divided into smaller, similar sub-problems.

Here are some common use cases for recursion:

  • Factorial calculation: A classic example where a number is multiplied by all integers below it.
  • Fibonacci series: A sequence where each number is the sum of the two preceding ones.
  • Tree traversal: Navigating through hierarchical structures like trees and graphs.
  • Searching: Recursive searching techniques in sorted or unsorted data.

What You'll Learn

In this guide, you'll learn the basics of recursion in Python. We'll walk through how recursive functions work, their structure, and how to apply recursion in various problems.

Understanding Recursive Functions

A recursive function calls itself with a smaller version of the original problem. It must have a base case, which is the condition where the function stops calling itself to prevent infinite recursion.

The basic structure of a recursive function looks like this:

python
def recursive_function(parameters):
    if base_case_condition:
        return result  # Base case: stop recursion
    else:
        return recursive_function(smaller_problem)  # Recursive call

The key points here are:

  • Base case: A condition where the function stops calling itself.
  • Recursive call: The function calls itself with a modified version of the original problem.

Example 1: Factorial Calculation

Here’s a simple example: calculating the factorial of a number. The factorial of a number n is the product of all positive integers less than or equal to n.

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

How It Works:

  • factorial: This is the recursive function used to calculate the factorial of a number.
  • n == 0: The base case where the recursion stops. The factorial of 0 is defined as 1.
  • The function calls itself with n-1, progressively reducing the problem until it hits the base case.

Output

120

Example 2: Fibonacci Sequence

Another classic example of recursion is the Fibonacci sequence. Each number in the sequence is the sum of the two preceding ones, starting from 0 and 1.

python
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive call
print(fibonacci(10))

How It Works:

  • fibonacci: This function calculates the nth Fibonacci number.
  • n <= 1: The base case, where the function returns n itself for n=0 or n=1.
  • The function calls itself twice, once with n-1 and once with n-2, and adds the results.

Output 

55

Example 3: Printing Numbers in Reverse

Here's a simple recursion example to print numbers from n to 1:

python
def print_reverse(n):
    if n > 0:
        print(n)
        print_reverse(n - 1)  # Recursive call
print_reverse(3)

How It Works:

  • print_reverse: The function prints numbers starting from n down to 1.
  • The function prints the current number and then calls itself with n-1 until n reaches 0.

Output 

3
2
1

Exercises

Try out the following exercises to practice using recursive functions in Python.

1. Write a recursive function to calculate the sum of digits in a number.
python
# Exercise 1: Sum the digits of a number using recursion
def sum_digits(n):
    if n == 0:
        return 0
    else:
        return n % 10 + sum_digits(n // 10)  # Sum the last digit and recurse with the remaining number

# Test the function
print(sum_digits(1234))  # Expected output: 10 (1 + 2 + 3 + 4)
2. Write a recursive function to find the greatest common divisor (GCD) of two numbers.
python
# Exercise 2: Find the greatest common divisor (GCD) using recursion
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)  # Recurse with b and the remainder of a divided by b

# Test the function
print(gcd(48, 18))  # Expected output: 6

*Tip: After completing an exercise, experiment with different inputs to test how your recursive function behaves.

Frequently Asked Questions

What is recursion in Python?

Recursion in Python refers to a method where a function calls itself to solve a problem. This technique helps break down complex problems into simpler sub-problems, which are easier to solve.

What is the base case in recursion?

The base case is a condition that stops the recursion. Without a base case, the function would continue to call itself indefinitely, leading to a stack overflow.

Why is recursion useful?

Recursion is useful when solving problems that can be divided into smaller, repetitive sub-problems, such as calculating the factorial of a number, traversing trees, or solving the Fibonacci sequence.

What happens if there is no base case in recursion?

If there is no base case, the recursive function will keep calling itself, leading to infinite recursion and eventually causing a stack overflow.

Can recursion be replaced by iteration?

Yes, some problems solved using recursion can be rewritten using iteration (loops). However, recursion often leads to cleaner, more elegant solutions, especially for problems like tree traversal or the Fibonacci sequence.

What's Next?

Next, you'll learn about docstrings, which are essential for documenting your code. Understanding how to write clear and concise docstrings will help you and others understand the purpose and functionality of your functions and classes.