recursion

Recursion is an area where "regular" developers tend to struggle a lot. Who could blame them, it's rare having to write recursive code at work. On the other hand, developers who've devoted time getting good at it can easily shine.

In my case, recursion was my weakest area, and quickly became one of my strongest.

Recursion Patterns

Pattern 0 - The base case.

Recursive functions need a base case. Without a base case, they just keep on going until the maximum recursion stack size is reached and the program stops.

1def func(depth = 0):
2  if depth >= 10:
3      return
4  print(depth)
5  func(depth + 1)

The program above prints the numbers 0 .. 9. The base case doesn't always have to be so explicit:

1def func(depth = 0):
2  if depth < 10:
3      print(depth)
4      func(depth + 1)

This achieves the same thing. We just don't do anything if the depth is 10 or greater. Please bear in mind in some cases we may want to return something explicitly in our base case, as opposed to None.

Pattern 1 - Building up the result in the return statement.

In our exploration of recursion, let's solve a simple problem: counting the nodes in a linked list.

1from dataclasses import dataclass
2
3@dataclass
4class ListNode:
5  val: int = 0
6  next: object = None
7
8head = ListNode(0, ListNode(1, ListNode(2)))

In this solution, the result is accumulated in the return statement:

1def count(n):
2  if n is None:
3      return 0
4  return 1 + count(n.next)
5
6print(count(head))

Pattern 2 - building up the result in an argument

Rather than accumulating in the return statement, we can do so in an argument being passed in.

1def count(n, size=0):
2  if n is None:
3      return size
4  return count(n.next, size + 1)
5
6print(count(head))

The advantage here is that the function knows where we are in the process.

Pattern 3 - recursion + iteration

This is a pattern you'll encounter all the time in Algorithmic Python: a recursive function that calls itself in a iterative section.

 1from dataclasses import dataclass, field
 2from typing import List
 3
 4@dataclass
 5class Tree:
 6 val: int = 0
 7 children: list = field(default_factory=list)
 8
 9head = Tree(0, [Tree(1), Tree(2, [Tree(3)])])
10
11def count(n):
12 if n is None:
13     return 0
14 counts = 1
15 for child in n.children:
16     counts += count(child)
17 return counts
18
19print(count(head))

n.b counts = 1. It may seem strange to start counting from 1, but that's because we have to account for ourselves. then accumulate the counts in our sub-trees. A more functional style would be:

1def count(n):
2  if n is None:
3      return 0
4  return 1 + sum(count(child) for child in n.children)
5
6print(count(head))