Recursion in Python is when a function calls itself to solve smaller parts of a bigger problem. This technique is useful when a task can be broken into simpler sub-tasks that look just like the original—like counting backwards, breaking down a number, or exploring nested lists and trees. It helps you solve problems by repeating the same pattern over and over. In this guide, we’ll learn how to write recursive functions using clear and fun examples, so you can understand how recursion works and start using it in your own Python projects.
Your First Recursive Function
Let’s start with a simple recursive function that counts down from a given number to zero. This shows the two most important parts of any recursive function: the base case, which stops the recursion, and the recursive case, where the function calls itself with a smaller input.
def countdown(n):
# Base case: when n is 0, stop recursion
if n == 0:
print("Liftoff!")
else:
# Print the current number
print(n)
# Recursive case: call countdown with n - 1
countdown(n - 1)
# Start the countdown from 5
countdown(5)This is the basic structure you’ll use again and again: check if you’ve reached the end (base case), and if not, call the function again with updated input.
Recursion vs Loops
In Python, many tasks can be done using either a loop or a recursive function. Let’s take the simple example of printing numbers from 1 to 5.
With a loop, the code is straightforward:
# Loop version: prints 1 to 5
for i in range(1, 6):
print(i)Now, here’s how you can do the same thing with recursion:
def count_up(n, max):
# Base case: stop when n goes past max
if n > max:
return
# Print current number
print(n)
# Recursive call: count up from the next number
count_up(n + 1, max)
# Start counting from 1 to 5
count_up(1, 5)Both approaches print the same result, but recursion gives us a different way of thinking—breaking down a task into smaller versions of itself. While loops repeat by structure, recursion repeats by calling itself until it hits a stopping point (called the base case).
Note: Loops are usually easier to read and better for simple, repeating tasks. Recursion shines when a problem naturally breaks down into smaller parts—like trees, nested data, or mathematical puzzles. If both work, loops are often the safer and more memory-efficient choice. But recursion can feel more elegant for the right kind of task.
Returning Values with Recursion
In this example, the recursive function sum_numbers calculates the sum of all numbers from 1 up to n. It uses a base case when n is 1 to stop the recursion, then adds n to the result of the smaller problem (sum_numbers(n - 1)). This way, the function builds the final result by returning values back up the call stack.
def sum_numbers(n):
if n == 1: # Base case: stop recursion when n is 1
return 1
return n + sum_numbers(n - 1) # Recursive case: add current n to sum of smaller numbers
print(sum_numbers(5)) # Output: 15Here, each recursive call waits for the next call to return its value. When the base case is reached, the function returns 1. Then, each waiting call adds its current number n to that returned value, passing the total back up. This process continues until the first call returns the final sum. This shows how recursion can build results step-by-step while moving back through the calls.
Factorial Example
The factorial of a number n is the product of all positive integers up to n. This classic example shows how recursion breaks down the problem: the factorial of n is n multiplied by the factorial of n - 1. The base case stops the recursion when n reaches 0, returning 1.
def factorial(n):
if n == 0: # Base case: factorial of 0 is 1
return 1
return n * factorial(n - 1) # Recursive case: n * factorial of (n - 1)
print(factorial(5)) # Output: 120Each call waits for the next smaller factorial to be calculated. When the base case returns 1, the calls multiply their current number by the returned result, building the final answer step-by-step. This example perfectly shows how recursion simplifies repetitive calculations.
Fun with Fibonacci
The Fibonacci sequence is a famous series where each number is the sum of the two before it. This simple recursive function shows how each Fibonacci number calls the two previous ones until it reaches the base cases 0 or 1.
def fib(n):
if n <= 1: # Base cases: fib(0) = 0, fib(1) = 1
return n
return fib(n - 1) + fib(n - 2) # Recursive case: sum of the two previous numbers
for i in range(10):
print(f"fib({i}) = {fib(i)}")This example helps you see how recursion can solve problems where the current result depends on multiple previous calls. Keeping the numbers small keeps it fun and easy to follow.
Working with Strings Recursively
Recursion isn’t just for numbers — it works great with strings too! Here’s a simple example that reverses a word by taking the first letter off and putting it at the end after reversing the rest.
def reverse(word):
if word == "": # Base case: empty string returns itself
return word
return reverse(word[1:]) + word[0] # Recursive step: reverse the rest + first letter
print(reverse("zebra")) # Output: arbezThis shows how recursion can process each part of a string step by step until everything is reversed. It’s a neat trick for string puzzles or text transformations!
Recursion on Lists
Recursion works well with lists too. Here’s how you can sum all the elements of a list by adding the first item to the sum of the rest.
def list_sum(lst):
if not lst: # Base case: empty list returns 0
return 0
return lst[0] + list_sum(lst[1:]) # Recursive step: first element + sum of the rest
print(list_sum([1, 2, 3, 4])) # Output: 10This example shows recursion breaking down a list one element at a time, making the problem simpler with each call until the list is empty.
Recursing Through Nested Structures
Recursion is perfect for nested structures like lists within lists. This example counts all the numbers inside a nested list, no matter how deep they go.
def count_all(data):
total = 0
for item in data:
if isinstance(item, list): # If item is a list, call count_all recursively
total += count_all(item)
else:
total += 1 # Count the item if it's not a list
return total
print(count_all([1, [2, 3], [4, [5, 6]]])) # Output: 6This function checks each item; if it’s a list, it dives deeper with recursion. If not, it adds to the count. It’s a neat way to explore all levels of nested data!
Check if a Word is a Palindrome
This recursive function checks if a word reads the same forwards and backwards—a palindrome. It compares the first and last letters, then keeps checking the middle part.
def is_palindrome(word):
if len(word) <= 1: # Base case: empty or single-letter word is a palindrome
return True
if word[0] != word[-1]: # If first and last letters differ, not a palindrome
return False
return is_palindrome(word[1:-1]) # Check the middle part recursively
print(is_palindrome("racecar")) # True
print(is_palindrome("banana")) # FalseThis keeps peeling off the outer letters until the word is too small to check, confirming if it’s a palindrome or not. Simple and clever!
Count Digits in a Number
This recursive function counts how many digits a number has by dividing it by 10 until it’s less than 10.
def count_digits(n):
if n < 10: # Base case: single-digit number
return 1
return 1 + count_digits(n // 10) # Count one digit and recurse with the rest
print(count_digits(12345)) # 5Each step removes the last digit by integer division, adding 1 to the count until only one digit remains. Simple and neat!
Find Maximum in a List
This recursive function finds the largest number in a list by comparing the first element with the maximum of the rest.
def find_max(lst):
if len(lst) == 1: # Base case: only one element
return lst[0]
rest_max = find_max(lst[1:]) # Max of the remaining list
return lst[0] if lst[0] > rest_max else rest_max # Compare and return larger
print(find_max([5, 9, 2, 1, 8, 3])) # 9It breaks down the list until a single element remains, then builds back up by comparing values.
Print a Pyramid Pattern
Here’s a fun way to print a simple star pyramid using recursion.
def pyramid(n):
if n == 0: # Base case: stop when n reaches 0
return
pyramid(n - 1) # Print smaller pyramid first (top)
print("*" * n) # Print stars for current level
pyramid(5)The function first prints the smaller levels, then the current level, creating a pyramid from top to bottom.
Binary Representation of a Number
This function converts a decimal number to its binary form as a string using recursion.
def to_binary(n):
if n == 0: # Base case: no more bits to process
return ""
return to_binary(n // 2) + str(n % 2) # Process higher bits first, then current bit
print(to_binary(10)) # 1010The number is divided by 2 repeatedly to get bits, building the binary string from left to right.
Flatten a Nested List
This recursive function takes a nested list with any depth and returns a flat list of all the elements.
def flatten(data):
flat = []
for item in data:
if isinstance(item, list): # If item is a list, flatten it recursively
flat += flatten(item)
else:
flat.append(item) # Otherwise, add the item directly
return flat
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]It keeps digging deeper whenever it finds a list, combining all elements into a single flat list.
Capitalize Words in a List
This example uses recursion to convert all words in a list to uppercase.
def capitalize_words(words):
if not words: # Base case: empty list returns empty list
return []
return [words[0].upper()] + capitalize_words(words[1:]) # Capitalize first word, then recurse on the rest
print(capitalize_words(['dog', 'cat', 'fox'])) # ['DOG', 'CAT', 'FOX']The function takes the first word, converts it, and then applies the same to the rest until the list is empty.
Repeat a Word N Times
This recursive function repeats a given word a specified number of times by calling itself until the count reaches zero.
def repeat(word, times):
if times == 0: # Base case: no more repetitions
return ""
return word + repeat(word, times - 1) # Add word and recurse
print(repeat("ho", 3)) # hohohoIt builds the repeated string step by step, adding one copy of the word each call.
Sum of Digits
This function recursively adds all digits in a number.
def digit_sum(n):
if n == 0: # Base case: no digits left
return 0
return n % 10 + digit_sum(n // 10) # Add last digit, then recurse on rest
print(digit_sum(1234)) # 10Each call separates the last digit, sums it, and continues with the remaining digits.
Build a Nested Countdown List
This function creates a nested list counting down from a number to zero, each level containing the current number and the next nested list.
def nested_countdown(n):
if n == 1:
return [1] # stop at 1
return [n, nested_countdown(n - 1)]
print(nested_countdown(5)) # Output: [5, [4, [3, [2, [1]]]]]Each recursive call builds a deeper nested list until zero is reached.
Count Vowels in a Word
This recursive function counts vowels in a given word by checking the first letter and then recursing on the rest.
def count_vowels(word):
if not word: # Base case: empty string
return 0
first = 1 if word[0].lower() in 'aeiou' else 0 # Check first letter
return first + count_vowels(word[1:]) # Add and recurse
print(count_vowels("Recursion")) # 4It sums up 1 for every vowel found and 0 for consonants, processing the word letter by letter.
Conclusion
Recursion is a powerful way to solve problems by breaking them down into smaller, similar tasks. The key is always to have a base case that stops the function from calling itself forever. Practicing simple examples helps you get comfortable with thinking about problems in this way. It’s exciting and fun to watch how a function can call itself repeatedly to work through a problem step by step, creating elegant solutions with just a few lines of code.