What is Recursion?

Overview

In computer science, Recursion is when a function calls itself. This process can repeat until a base condition is met, preventing the call stack from growing indefinitely (discussed below).

Call Stack

The call stack is a stack data structure in memory that is reserved to track a thread’s execution. Each thread has one. This is in contrast to heap space, that is shared by all threads. This fact exists in multiple programming languages, including Python and Java. However, to use Python and Java as examples, the size of Python’s call stack is determined by recursion depth while the size of Java’s call stack is determined by size in memory.

Use Cases

Recursive functions make calls to themselves in a DFS (Depth-First Search) manner. DFS Backtracking is a popular use case for recursive functions. But there are more:

• Tree data structure traversals (rather than just a problem space tree, as we can learn in the DFS Backtracking post) (e.g. DFS Tree Traversal).
• Graph traversals (e.g. DFS Graph Traversals).
• Divide and Conquer algorithms (e.g. Merge Sort).
• Dynamic Programming (e.g. Memoized DFS Backtracking).

Fundamentals

A basic recursive function typically has two parts:

• The base case.
• The recursive case.

The base case is meant to end the function’s recursion. An example in calculating the nth item in the Fibonacci sequence is:

# n in the sequence is 0-indexed 
def fibonacci(n): 
  if n < 2: 
    return 1 
  return fibonacci(n - 1) + fibonacci(n - 2) 

In the above example, if n < 2: return 1 is the base case and return fibonacci(n - 1) + fibonacci(n - 2) is the recursive case. However, we could simplify the above function even more to make the base case less obvious:

# n in the sequence is 0-indexed 
def fibonacci(n): 
  return fibonacci(n - 1) + fibonacci(n - 2) if n > 1 else 1 

In the above alternative, else 1 is the base case.

Memoization

The above Fibonacci function will necessarily create a tree of recursive calls that looks like a tree. This is explained in greater detail in DFS Backtracking. There will be repetitive calls as is obvious from the fact that the only number being returned is 1 (in the first example). Memoization can help to reduce repetitive function calls by storing the value of previous calls and returning them when the same arguments are encountered. This reduction in repetitive function calls (that are encountered in different locations in the recursion call tree) significantly improves performance. For example:

memo = {}
# n in the sequence is 0-indexed 
def fibonacci(n): 
  if n in memo:
    return memo[n]
  if n < 2: 
    return 1 
  memo[n] = fibonacci(n - 1) + fibonacci(n - 2) 
  return memo[n]

Alternatively, we could use Python’s @cache decorators in its built-in functools library.

Iterative Alternative

There are cases when a recursive algorithm breaks because it reaches the call stack limit. Significant changes are not required. The arguments provided to the function’s parameters can be provided as tuples to a literal stack that is iterated over in a while loop.

Iterative alternatives are typically more verbose (in terms of code readability), so for maintainability, recursive solutions are typically preferred. However, recursive solutions use more memory given their usage of the call stack. Recursive solutions usually win this tradeoff unless the use case is embedded systems where memory is very scarce.

Conclusion

Recursion is an important concept in computer science. It opens the door to the idea of creating solutions to problem by breaking them down into sub-problems that may or may not have overlapping solutions. If they do, then it can be considered to be Dynamic Programming.

Learn more about Dynamic Programming: Dynamic Programming Matrix.

To be updated with more examples and diagrams.

Author

Sam Malayek works in Vancouver, using this space to fill in a few gaps. Opinions are his own.

• ← What is a Service Mesh?
• Authorization Middleware →