Python Recursion
Hello there, Python enthusiasts! Today we’re diving into the magical world of recursion. If you’ve been coding in Python for a while, you’ve probably heard of recursion, but do you really understand it? Well, fear not! We’re here to unravel the mysteries of recursion in Python and show you how it can be a powerful tool in your programming toolbox.
Table of Contents
Understanding Recursion in Python
Recursion, in the simplest terms, is a method where the solution to a problem depends on solutions to smaller instances of the same problem. In Python, this translates to a function that calls itself to solve a problem. Sounds like magic, right? But it’s actually a fundamental concept in computer science and is used in various algorithms and data structures.
Anatomy of a Recursive Function
Let’s break down a recursive function in Python. A recursive function consists of two main components: a base case and a recursive case. The base case is the condition that stops the recursion, while the recursive case is where the function calls itself.
Here’s a simple example of a recursive function that calculates the factorial of a number:
def factorial(n):
# Base case: 1 factorial is 1
if n == 1:
return 1
# Recursive case: n factorial is n times (n1) factorial
else:
return n * factorial(n1)
print(factorial(5))
PythonIn this example, the base case is when n
is 1. In this case, the function returns 1 because the factorial of 1 is 1. The recursive case is when n
is greater than 1. In this case, the function returns n
multiplied by the factorial of n1
. This is because the factorial of a number n
is the product of n
and the factorial of n1
.
Here’s another example of a recursive function that calculates the sum of all numbers up to n
:
def sum_up_to_n(n):
# Base case: sum up to 1 is 1
if n == 1:
return 1
# Recursive case: sum up to n is n plus sum up to (n1)
else:
return n + sum_up_to_n(n1)
print(sum_up_to_n(5))
PythonIn this example, the base case is when n
is 1. In this case, the function returns 1 because the sum of all numbers up to 1 is 1. The recursive case is when n
is greater than 1. In this case, the function returns n
plus the sum of all numbers up to n1
. This is because the sum of all numbers up to n
is n
plus the sum of all numbers up to n1
.
Recursive Algorithms in Python
Recursive algorithms are algorithms that solve problems by solving smaller instances of the same problem. Some common examples of recursive algorithms include the Fibonacci sequence, binary search, and tree traversal algorithms. These algorithms are often more straightforward and easier to understand when implemented recursively.
Python Recursion Limit
But wait, there’s a catch! Python sets a limit on the maximum depth of recursion to prevent a stack overflow. However, the good news is that this limit can be changed using the sys
module’s setrecursionlimit()
function. But be careful, increasing the recursion limit can lead to a crash if too much memory is used!
Practical Examples of Python Recursion in Data Structures
Now that we’ve got the theory down, let’s look at some practical examples of recursion in Python data structures.
Factorial Calculation
Let’s start with a classic example of recursion: 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
. It’s often denoted as n!
. For example, the factorial of 5 (denoted as 5!) is 5 * 4 * 3 * 2 * 1 = 120
.
Here’s how we can calculate the factorial of a number using recursion in Python:
def factorial(n):
# Base case: if n is 0 or 1, return 1
if n == 0 or n == 1:
return 1
# Recursive case: n factorial is n times (n1) factorial
else:
return n * factorial(n1)
PythonIn this code, the base case is when n
is 0 or 1. In this case, the function returns 1 because the factorial of 0 or 1 is 1. The recursive case is when n
is greater than 1. In this case, the function returns n
multiplied by the factorial of n1
.
Let’s test our function with some examples:
def factorial(n):
# Base case: if n is 0 or 1, return 1
if n == 0 or n == 1:
return 1
# Recursive case: n factorial is n times (n1) factorial
else:
return n * factorial(n1)
print(factorial(5)) # Output: 120
print(factorial(3)) # Output: 6
print(factorial(0)) # Output:
PythonAs you can see, our recursive function correctly calculates the factorial of a number.
Fibonacci Sequence
Another classic example of recursion is generating the Fibonacci sequence. The Fibonacci sequence is a series of numbers where a number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.
Here’s how we can generate the Fibonacci sequence using recursion in Python:
def fibonacci(n):
# Base case: if n is 0 or 1, return n
if n == 0 or n == 1:
return n
# Recursive case: nth Fibonacci number is (n1)th Fibonacci number plus (n2)th Fibonacci number
else:
return fibonacci(n1) + fibonacci(n2)
PythonIn this code, the base case is when n
is 0 or 1. In this case, the function returns n
because the 0th and 1st Fibonacci numbers are 0 and 1, respectively. The recursive case is when n
is greater than 1. In this case, the function returns the sum of the (n1)
th and (n2)
th Fibonacci numbers.
Let’s test our function with some examples:
def fibonacci(n):
# Base case: if n is 0 or 1, return n
if n == 0 or n == 1:
return n
# Recursive case: nth Fibonacci number is (n1)th Fibonacci number plus (n2)th Fibonacci number
else:
return fibonacci(n1) + fibonacci(n2)
print(fibonacci(5)) # Output: 5
print(fibonacci(7)) # Output: 13
print(fibonacci(10)) # Output: 55
PythonAs you can see, our recursive function correctly generates the Fibonacci sequence.
Binary Search
Binary search is a search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half until it is successful or the remaining half is empty.
Here’s how we can implement binary search using recursion in Python:
Binary search is a search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array and based on the comparison, it can eliminate half of the search space.
In following example, we are searching for the element 7
in the array arr
. The initial values for low
and high
are 0
and len(arr)1
, respectively, which represent the entire range of the array.
def binary_search(arr, low, high, x):
# Base case: low > high
if high >= low:
mid = (high + low) // 2
# If element is present at the middle
if arr[mid] == x:
return mid
# If element is smaller than mid
elif arr[mid] > x:
return binary_search(arr, low, mid  1, x)
# Else the element is in right
else:
return binary_search(arr, mid + 1, high, x)
else:
# Element is not present in array
return 1
# Example function call
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
x = 7
result = binary_search(arr, 0, len(arr)1, x)
if result != 1:
print(f"Element {x} is present at index {result}")
else:
print(f"Element {x} is not present in the array")
PythonThe result of the recursive binary search function call is:
“Element 7 is present at index 6”
This binary search function uses recursion to repeatedly divide the search space in half until the target value is found or until the search space is empty (i.e., low > high
).
Tree Traversal
Tree traversal is another area where recursion shines. In a tree data structure, elements are arranged in a hierarchical structure. Traversing this structure can be done recursively in several ways, including preorder, inorder, and postorder traversal.
Here’s a simple example of a recursive function for inorder tree traversal:
Code:
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def in_order_traversal(node):
if node:
# First recur on left child
in_order_traversal(node.left)
# Then print the data of node
print(node.value),
# Now recur on right child
in_order_traversal(node.right)
# Create nodes
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# Perform inorder traversal
in_order_traversal(root)
PythonExplanation:
Let’s break down the provided code and its function call:
1. Node Class
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
Explanation:
 The
Node
class is used to represent each individual node of the binary tree.  Each node has three attributes:
value
: Stores the actual value/data of the node.left
: A reference to the left child of the node.right
: A reference to the right child of the node. The
__init__
method initializes a node with a given value and sets itsleft
andright
attributes toNone
(indicating it doesn’t have any children yet).
2. InOrder Traversal Function
def in_order_traversal(node):
if node:
in_order_traversal(node.left)
print(node.value, end=" > "),
in_order_traversal(node.right)
Explanation:
 The
in_order_traversal
function is a recursive function that performs an inorder traversal on a binary tree.  The inorder traversal sequence is: Left Child > Root > Right Child.
 The function starts by checking if the current node (
node
) exists.  If the node exists, it first recursively calls itself on the left child (
in_order_traversal(node.left)
).  After traversing the left subtree, it prints the value of the current node.
 Finally, it recursively calls itself on the right child (
in_order_traversal(node.right)
).
3. Creating the Binary Tree and Function Call
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
in_order_traversal(root)
Explanation:
 We start by creating the root node of the binary tree with a value of
1
.  We then create the left child of the root with a value of
2
and the right child with a value of3
.  For the left child (node with value
2
), we further create its left and right children with values4
and5
, respectively. This gives us a binary tree that looks like:
1
/ \
2 3
/ \
4 5
 We then call the
in_order_traversal
function with the root node as its argument. This initiates the recursive inorder traversal process, and the nodes are printed in the sequence: 4, 2, 5, 1, 3.
I hope this stepbystep explanation provides a clear understanding of the provided code, its structure, and its functioning!
Conclusion
And there you have it! You’ve just journeyed through the magical world of recursion in Python. From understanding the basics to exploring practical examples in data structures, we hope this guide has given you a solid foundation in Python recursion. Remember, like any powerful tool, recursion is best used judiciously. But with practice, you’ll be able to wield it effectively to write cleaner and more efficient code. Happy coding!
Frequently Asked Questions (FAQ)

What is recursion in Python?
Recursion in Python is a method where the solution to a problem depends on solutions to smaller instances of the same problem. This is achieved by a function calling itself during its execution, known as a recursive call.

How does a recursive function work?
A recursive function works by calling itself to solve a problem. It consists of two main components: a base case and a recursive case. The base case is the condition that stops the recursion, while the recursive case is where the function calls itself.

What is the base case in recursion?
The base case in recursion is the condition that stops the recursion. It’s the simplest form of the problem that can be solved directly without further recursion.

What is a recursive case in recursion?
The recursive case in recursion is where the function calls itself to solve a problem. It breaks down complex problems into simpler instances of the same problem.

What is the Python recursion limit?
Python sets a limit on the maximum depth of recursion to prevent a stack overflow. This limit can be changed using the
sys
module’ssetrecursionlimit()
function. 
What are some examples of recursive algorithms?
Some common examples of recursive algorithms include the Fibonacci sequence, binary search, and tree traversal algorithms. These algorithms are often more straightforward and easier to understand when implemented recursively.

How is recursion used in data structures?
Recursion is used in data structures to solve problems that can be broken down into simpler instances of the same problem. For example, in tree traversal, recursion is used to visit each node in the tree by recursively visiting each node’s children.

What is the difference between recursion and iteration?
Recursion and iteration are both programming techniques used to repeat a sequence of instructions. The main difference is that recursion involves a function calling itself to repeat the sequence, while iteration uses a loop structure (like a
for
orwhile
loop) to repeat the sequence. 
Can every recursive algorithm be written iteratively?
Yes, every recursive algorithm can be written iteratively and vice versa. However, some problems are more naturally solved using recursion, while others are more straightforward with iteration. The choice between recursion and iteration often depends on the specific problem and the programmer’s preference.