Olivia A. Gallucci

Recursion is where a function calls itself during its execution, and it can lead to concise solutions when applied correctly. This blog post explores recursion, and its significance in algorithm analysis.

Recursive paradigm

The recursive paradigm involves breaking a problem into smaller instances of the same problem. Each recursive call solves a smaller subproblem, eventually leading to the base case – a condition where the problem becomes trivial and does not require further recursion.

Self-similarity

Self-similarity is the characteristic of a pattern or object to exhibit similar structures or features at different scales or levels of magnification. 

Recursion often reveals self-similarity within the problem at hand. The structure of the solution mirrors the structure of the problem itself.

Divide and conquer

The recursive approach is akin to the “divide and conquer” strategy, where a problem is divided into more straightforward subproblems. 

Each recursive call is an invocation to solve a smaller* instance of the problem, eventually converging towards a base case where the problem becomes trivial to solve. This division and subsequent conquering of smaller subproblems lay the foundation for an algorithm’s recursive nature.

For instance, consider the process of folding a piece of paper in half multiple times.

1. Start with an unfolded piece of paper.
2. Fold it in half once, creating two layers.
3. Then, fold it in half again. Now, you have four layers.
4. Continue folding it in half multiple times.

This process is recursive because each step involves repeating the same action (folding the paper in half) on a smaller version of the original problem (the folded paper). Each fold doubles the number of layers, creating a pattern that can continue indefinitely, though practically limited by the thickness of the paper and physical constraints.

* Recursion sometimes doesn’t result in a smaller version of the same problem. In other words, not all recursive algorithms are divide and conquer; they can have various structures and purposes. While divide-and-conquer is a paradigm that involves breaking a problem into subproblems, solving them recursively, and combining the results, other recursive algorithms involve backtracking, dynamic programming, or simple recursive calls without a clear divide and conquer strategy.

Visual recursion example 

Source.

Now, let’s look at a coding example. Consider sorting an array using the merge sort algorithm (video). Each recursive call divides the array into two halves, sorts each half separately, and then, merges them back together. This recursive example captures the decomposition of a larger problem into smaller, more manageable subproblems.

	def merge_sort(arr):
	if len(arr) <= 1:
	return arr
	# split array in half
	middle = len(arr) // 2
	left_half = arr[0:middle]
	right_half = arr[middle:]
	# recursively sort each half
	left_half = merge_sort(left_half)
	right_half = merge_sort(right_half)
	# merge the sorted halves
	result = merge(left_half, right_half)
	return result
	def merge(left, right):
	result = []
	while len(left) > 0 and len(right) > 0:
	if left[0] <= right[0]:
	result.append(left[0])
	left = left[1:]
	else:
	result.append(right[0])
	right = right[1:]
	# if there are any remaining
	# elements in either left or right
	result += left
	result += right
	return result
	def main():
	arr = [12, 11, 13, 5, 6, 7]
	sorted_arr = merge_sort(arr)
	print("sorted arr:", sorted_arr)
	# sorted arr: [5, 6, 7, 11, 12, 13]
	if __name__ == "__main__":
	main()

view raw recursiveMergeSort.py hosted with ❤ by GitHub

Recursive call stack

One fundamental aspect of recursion is the call stack: a dynamic data structure that manages function calls. As each recursive call is made, a new frame* is added to the call stack. 

A recursive call stack specifically refers to the organization of function calls when a function calls itself.

Understanding the call stack is crucial for recursive algorithm analysis because it governs the flow of function calls, tracks local variables, and ensures the correct unwinding of calls, impacting both efficiency and correctness of the solution.

* A frame is a data structure containing information about a specific function call. It typically includes details like the function’s parameters, local variables, and the return address where the program should continue execution after the function call completes. Each time a function is called, a new frame is created and added to the call stack. When the function completes execution, its frame is removed from the stack, allowing the program to return to the previous function call. Frames represent each function call’s state within the program’s execution flow.

Break down 

Here is a break down of a call stack, and how it works in the context of recursion:

1. Call stack
   1. The call stack is a region of memory that stores information about the active functions in a program.
   2. Each time a program calls a function, the call stack creates a new frame and pushes it onto the top of the call stack.
   3. The frame contains information—such as the function’s local variables, parameters, and the address—to return to once the function completes.
2. Function calls
   1. When a program calls a function, the call stack creates a new frame and pushes it onto the stack.
   2. The program counter (or instruction pointer) is set to the first line of code in the called function.
   3. The function’s execution proceeds within its own frame on top of the stack.
3. Recursive calls
   1. In recursion, a function calls itself, creating a new instance of the function.
   2. Each recursive call creates a new frame on top of the previous frames on the stack.
   3. The function’s execution continues within the new frame.
4. Base case
   1. To avoid infinite recursion, recursive functions typically include a base case: a condition that, when met, prevents further recursive calls.
   2. When the program’s execution reaches the base case, the function starts to return, and each return removes a frame from the top of the stack.
5. Stack unwinding
   1. As the program reaches the base case, the function returns, and the call stack begins to unwind.
   2. Each return removes a frame from the top of the stack, and the control is passed back to the calling function.
   3. The stack unwinding continues until the initial function call is reached.

Example 

Below, there is an example of a recursive call stack. In this example, factorial is a recursive function that calculates the factorial of a number. The call stack populates with frames for each recursive call, and as it reaches the base case, the stack will unwind, eventually producing the result.

	def factorial(n):
	if n == 0:
	return 1
	else:
	return n * factorial(n – 1)
	def main():
	result = factorial(5)
	print("result:", result)
	# result: 120
	if __name__ == "__main__":
	main()

view raw recursiveCallStackExample.py hosted with ❤ by GitHub

In short, as recursive calls unfold, they are controlled by the call stack, a dynamic data structure tracking of the function calls. Understanding the interplay between recursive calls and the call stack is important for understanding recursion and analyzing its efficiency. 

Types of recursion 

There are several types of recursion. Each type captures a different way in which functions can call themselves. 

Linear or direct recursion

In linear recursion, a function calls itself exactly once. The recursive call may be the last operation in the function or might involve additional computations afterward.

	def factorial(n):
	if n == 0:
	return 1
	else:
	return n * factorial(n – 1)
	def main():
	result = factorial(5)
	print("result:", result)
	# result: 120
	if __name__ == "__main__":
	main()

view raw recursiveCallStackExample.py hosted with ❤ by GitHub

	def linear_recursion(n):
	if n > 0:
	print(n)
	linear_recursion(n – 1)
	def main():
	n = 5
	linear_recursion(n)
	if __name__ == "__main__":
	main()
	# prints
	# 5
	# 4
	# 3
	# 2
	# 1

view raw linearRecursion.py hosted with ❤ by GitHub

Tail recursion and memory usage 

Recursion can be memory-intensive due to the call stack, especially for deep recursion. However, tail recursion can mitigate this issue. 

Tail recursion is a specific type of linear recursion where the recursive call is the last operation in the function. It optimizes memory usage by reusing the same stack frame for each recursive call, eliminating the need to store multiple stack frames and preventing stack overflow in some instances. 

A stack overflow error occurs when a program’s call stack, used for managing function calls and local variables, exceeds its available memory, typically due to excessive recursion or deeply nested function calls.

In other words, tail-recursive functions can be optimized by compilers to use constant stack space, leading to better performance.

	def tail_recursion(n, acc=0):
	if n == 0:
	return acc
	else:
	return tail_recursion(n – 1, acc + n)
	def main():
	n = 10
	result = tail_recursion(n)
	print("sum of ints from 1 to " + str(n) + " is: " + str(result))
	# sum of ints from 1 to 10 is: 55
	if __name__ == "__main__":
	main()

view raw tailRecursionExample.py hosted with ❤ by GitHub

Multiple recursion

In multiple recursion, a function may make more than one recursive call during its execution. Multiple recursion is often helpful when a problem can be divided into multiple subproblems, each of which is solved recursively.

	def multiple_recursion(n):
	if n <= 0:
	return
	print(n)
	multiple_recursion(n – 1)
	multiple_recursion(n – 2)
	def main():
	n = 4
	print("Output:")
	multiple_recursion(n)
	if __name__ == "__main__":
	main()
	# Output:
	# 4
	# 3
	# 2
	# 1
	# 1
	# 2
	# 1

view raw multipleRecursionExample.py hosted with ❤ by GitHub

Binary recursion

Binary recursion involves breaking a problem into two subproblems, and each subproblem is solved recursively. This type of recursion is often used in divide-and-conquer algorithms.

	def binary_search(arr, target, low, high):
	if low > high:
	# base case: element not found
	return -1
	mid = (low + high) // 2
	if arr[mid] == target:
	# base case: element found at mid index
	return mid
	elif arr[mid] < target:
	# recur right half
	return binary_search(arr, target, mid + 1, high)
	else:
	# recur left half
	return binary_search(arr, target, low, mid – 1)
	# example
	arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
	target = 14
	result = binary_search(arr, target, 0, len(arr) – 1)
	if result != -1:
	print("element " + str(target) +
	" found at index " + str(result))
	else:
	print("element " + str(target) + " not found in arr")
	# prints
	# element 14 found at index 6

view raw binaryRecursionExample.py hosted with ❤ by GitHub

Indirect recursion

Indirect recursion occurs when a function calls another function, and eventually, the second function calls the first function, creating a loop of recursive calls between two or more functions.

	def indirect_recursion_a(n):
	if n > 0:
	print("A: " + str(n))
	indirect_recursion_b(n – 1)
	def indirect_recursion_b(n):
	if n > 0:
	print("B: " + str(n))
	indirect_recursion_a(n – 1)
	# example
	result = indirect_recursion_a(5)
	print(result)
	# prints:
	# A: 5
	# B: 4
	# A: 3
	# B: 2
	# A: 1
	# None

view raw indirectRecursionExample.py hosted with ❤ by GitHub

Nested recursion

Nested recursion is when a function calls itself as an argument to another invocation of the same function.

	def nested_recursion(n):
	if n > 100:
	return n – 10
	else:
	# here is the nesting
	return nested_recursion(nested_recursion(n + 11))
	result = nested_recursion(95)
	print(result)
	# prints
	# 91

view raw nested_recursion.py hosted with ❤ by GitHub

Time complexity: recurrence relations and Master Theorem

Recursion introduces a tradeoff between simplicity and efficiency (aka, time complexity). To understand these tradeoffs, I recommend learning two techniques—recurrence relations and Master Theorem—to analyze the time complexity of recursive algorithms.

Read more: Recurrence Relations: Measuring Efficiency and Optimization and Using Master Theorem Components and Formulations

Pitfalls of recursion

Recursion is not a one-size-fits-all solution. Some situations where recursion might pose challenges include deep recursion, missing base case, repeated work, function call overhead, and limited tail call optimization. 

Deep recursion

Issue	Mitigation
Recursion involves creating a new stack frame for each recursive call. If the recursion goes too deep, it can result in a large number of stacked function calls, consuming a significant amount of memory.	Developers can limit recursion depth or consider converting the recursive algorithm into an iterative one. Tail recursion optimization can be optimized by some compilers to use constant stack space.

Tail recursion optimization is where the recursive call is the last operation in the function. 

Missing base case

Issue	Mitigation
If the base case is not correctly defined or omitted, the recursion may never terminate, leading to an infinite loop. In other words, the program will run forever until it crashes or is forcefully stoped.	Developers should define a proper base case, and meet all termination conditions.

Repeated work

Issue	Mitigation
Recursive algorithms may redundantly perform the same computations multiple times, leading to inefficiencies.	Memorization or caching can store and reuse the results of previous recursive calls, reducing redundant computations. This technique is often associated with dynamic programming.

Function call overhead

Issue	Mitigation
Function call overhead in some programming languages is significant. With a large number of recursive calls, this overhead can impact performance.	Developers may use iterative solutions or optimization techniques, like loop unrolling, to reduce function call overhead.

Limited tail call optimization

Issue	Mitigation
Some programming languages may not support tail call optimization (TCO), which is a technique that allows the compiler to optimize tail-recursive calls and reuse the current function’s stack frame.	Developers using languages that lack TCO may need to manually convert tail-recursive functions into iterative ones to avoid stack overflow errors.

Programming language constraints on recursion

In addition to the pitfalls of recursion itself, constraints of programming languages can interfere with recursion due to limitations in the language’s support for recursion-related features. This section will explore some factors to consider. 

Stack size limitations

Issue: Some programming languages impose a limit on the size of the call stack. If recursion goes too deep, it may exceed this limit and result in a stack overflow error.

Example: In languages like C and C++, which may have smaller default stack sizes, deep recursion can lead to stack overflow more easily than in languages like Python or Java.

Lack of TCO

Issue: Remember, TCO is a technique that allows the compiler to optimize tail-recursive calls, reusing the current function’s stack frame. Languages lacking TCO may lead to stack overflow errors with deep recursion.

Example: Functional programming languages like Scheme and Haskell often support TCO, making them well-suited for specific recursive patterns. In contrast, languages like Java or C# may not provide native TCO, affecting the performance of tail-recursive functions.

Function call overhead

Issue: Some languages have higher function call overhead. In other words, making a function call is relatively computationally expensive in these languages. This overhead can impact performance in the context of recursion.

Example: In languages like Python, where function calls have more overhead than C or C++, developers should consider the performance implications when implementing recursive algorithms.

Memory management policies

Issue: Some languages have specific memory management policies that can impact the efficiency of recursive algorithms, especially if they involve creating and managing a large number of objects on the heap.

The heap is a tree-based data structure that satisfies the heap property, typically used to implement priority queues.

Example: In languages with automatic garbage collection, such as Java or C#, the overhead of managing memory may be higher compared to languages like C++ with manual memory management. Manual memory management can affect the efficiency of recursive algorithms that generate a large number of objects. 

Example scenario

Suppose you are traversing a deep tree structure (aka has a high depth) and must implement a recursive algorithm. If the tree is shallow (aka has a low depth), the programming language’s support for recursion might not be a significant concern. 

However, if the tree is extremely deep, a language with good tail call optimization or a larger default stack size may be preferable to avoid stack overflow errors. In this case, a language like Scheme or Haskell, which supports TCO, might be preferred over a language like C, which lacks TCO and may have a smaller default stack size.

Ultimately, the choice of programming language depends on the characteristics of the problem, the performance requirements, and the language features that support or hinder the efficient implementation of recursive algorithms.

Conclusion 

By breaking problems into smaller, self-similar subproblems, recursion helps tackle complexity. As this series on analysis of algorithms continues, I hope my readers can let the recursive mindset be a guiding light. :) 

If you enjoyed this post on recursion, consider reading Asymptotic Notation: Big O, Omega, and Theta.