Recursion refers to defining something in terms of itself. In a programming context it usually refers to a function which calls itself. For this to work without causing any infinite loops, the arguments passed to the function must change each time, so that the nested function calls will stop at some point. The basic principle here is the same as in while loops: there must always be a stop condition of some kind, and that condition must be triggered at some point in the execution.
Iterative vs Recursive solutions
Iterative algorithms are based on sequential processing of items, using loops. Recursive algorithms are ones in which a function calls itself with a change in arguements. In practice, deciding an iterative solution or a recursive solution depends on the problem; certain problems are more suited to one type than the other.
example of the Fibonacci sequence, a famous recursive algorithm:
def fibonacci(n: int):
""" The function returns the nth number in the Fibonacci sequence (1, 1, 2, 3, 5, 8 etc.); n > 0"""
if n <= 2:
# aka the "base case"
# the first two are ones
return 1
# All other numbers equal the sum of the two preceding numbers in the sequence
return fibonacci(n - 1) + fibonacci(n - 2)
if __name__ == "__main__":
for i in range(1, 11):
print(f"The {i}. number in the Fibonacci sequence is {fibonacci(i)}")Some recursive algorithms
Here I will note down some recursive algorithms, and whether alternatives exist for them, and how recursion is achieved.
Binary Search
In Binary Search there’s a sorted list (descending or ascending, below code is only for ascending) and there’s a target value. We need to find the target value within that sorted list. The idea is simple: we pick out the middle/center element during each pass and we decide if the target element is greater or lesser than it (we can only do this because the list is sorted). If the target element is smaller than the center element, we reduce the search area to the left bound to the (center-1)th element. If the target element is larger than the center element, we reduce the search area to the (center+1)th element all the way to the right bound. We then perform binary search again (RECURSIVELY) in one of these search areas.
examples for both iterative and recursive algorithms:
import time
def binary_search(sorted_list: list, target: int, left: int, right: int):
# we assume that left is index 0 and right is len(sorted_list) - 1
if left > right:
return False
middle = (left + right) // 2
if target == sorted_list[middle]:
return True
elif target > sorted_list[middle]:
return binary_search(sorted_list, target, middle+1, right)
elif target < sorted_list[middle]:
return binary_search(sorted_list, target, left, middle - 1)
def binary_search_iter(sorted_list: list, target: int):
left = 0
right = len(sorted_list) - 1
while left <= right:
middle = (left + right) // 2
if target == sorted_list[middle]:
return True
elif target > sorted_list[middle]:
left = middle + 1
elif target < sorted_list[middle]:
right = middle - 1
if __name__ == "__main__":
number = int(input("How many items do you want to be there in the list: "))
sorted_list = [num for num in range(0, number)]
target = int(input("What to search for: "))
t1 = time.perf_counter()
print(binary_search(sorted_list, target, 0, len(sorted_list)-1))
t2 = time.perf_counter()
print(f"Recursive binary search: {(t2 - t1) * 1e6:.3f} µs")
t3 = time.perf_counter()
print(binary_search_iter(sorted_list, target))
t4 = time.perf_counter()
print(f"Iterative binary search: {(t4 - t3) * 1e6:.3f} µs")Binary Trees
A binary tree is a branched structure where we have nodes, and at each node the structure branches, at most, into two child branches with nodes of their own.
Binary trees are by nature recursive, as each “subtree” is another binary tree:
In theory, any recursive algorithm for a binary tree must do these three things:
- Process the current node
- Call itself on the child node on the left
- Call itself on the child node on the right
There are also special kinds of binary trees, that is sorted binary trees where the left child of each node is smaller than the node itself, and the right child is correspondingly greater.
some examples of algorithms for binary trees:
# modeling binary trees
from __future__ import annotations
class Node:
"""This class models a single node in a binary tree"""
def __init__(
self,
value: int,
right_child: Node | None = None,
left_child: Node | None = None,
):
self.value = value
self.left_child = left_child
self.right_child = right_child
def greatest_node(root: Node):
greatest = root.value
if root.left_child is not None:
if greatest_node(root.left_child) > greatest:
greatest = greatest_node(root.left_child)
if root.right_child is not None:
if greatest_node(root.right_child) > greatest:
greatest = greatest_node(root.right_child)
return greatest
def print_nodes(root: Node):
print(root.value)
if root.left_child is not None:
print_nodes(root.left_child)
if root.right_child is not None:
print_nodes(root.right_child)
def sum_nodes(root: Node):
node_sum = root.value
if root.left_child is not None:
node_sum += sum_nodes(root.left_child)
if root.right_child is not None:
node_sum += sum_nodes(root.right_child)
return node_sum
def find_node(root: Node | None, value: int):
""" Finds a node in a sorted Binary tree"""
if root is None:
return False
if root.value == value:
return True
if root.value < value:
return find_node(root.right_child, value)
if root.value > value:
return find_node(root.left_child, value)
if __name__ == "__main__":
# modeling a simple binary tree
# 2
# / \
# 3 4
# /\ /\
# 1 2 5 11
tree = Node(2)
tree.left_child = Node(3)
tree.right_child = Node(4)
tree.left_child.left_child = Node(1)
tree.left_child.right_child = Node(2)
tree.right_child.left_child = Node(5)
tree.right_child.right_child = Node(11)
print_nodes(tree)
print(sum_nodes(tree))When to use
Recursion should be used when a problem is inherently recursive, like trees or other sorting algorithms. But it should not be used generally as it generally has a greater memory overhead (extra stack frames per call) than iterative methods.