What is recursion
Recursion is like brocolli (or cauliflower).
Recursion is a function that is defined with itself. \(f(n) = \text{some combination of }f(n-1)\). What does that supposed to mean?
The simplest example I think is the natural number sequence \(1, 2, 3, 4, 5, 6, ...\)
An important tip: don’t be intimated by recursions. Insert as many print statements as you need to see what the program is doing.
Natural number
The natural numbers can be expressed as:
\(f(n)=f(n-1)+1\), with the initial condition that the first number is \(0\) (when \(n=0\)).
The initial values must be given in order for the recursion to be fully defined.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| f(n) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
if input is equal to initial value, then return the values for initial values else return the mathematical function
Translate it to code.
If (initial) input value is \(0\), output is \(1\). Else output the (value generated by) the mathematical formula.
In runtime, the recursive formula will unwind layer by layer (stacks) until the initial values.
An aside: when most programs run, they allocate a single chunk of memory. In Python, recursion is a lot slower to run than iterations using loops.
def f(n):
if n == 0:
return 1
else:
return f(n-1) + 1
for i in range(10):
print(f(i))
Fibonacci number
The Fibonacci numbers can be expressed as:
\(F_1 = F_2 = 1\),
\[F_n=F_(n-1) + F_(n-2)\]with the initial condition that the first and the second numbers \(1\) and \(1\) (when \(n=0\) and \(n=1\)). Again, the initial values must be given in order for the recursion to be fully defined.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| fib(n) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
def fib(n):
if (n== 0)|(n==1):
return 1
else:
return fib(n -1) + fib(n-2)
for i in range(10):
print(fib(i))
# lt = []
# for i in range(10):
# print(fib(i))
# lt.append(fib(i))
# df = pd.DataFrame({'fib(n)':lt})
# print(df.T.to_markdown())
Factorial
The factorial is another simple example. \(n! = n*(n-1)*...*1\)
def fact(n):
if n < 0:
return -1
elif n == 1:
return 1
else:
return n*fact(n-1)
print(fact(5))
# 120
Greatest common divisor (GCD)
Two integers, \(a\) and \(b\), what is their greatest common divisor (GDC)?
In my view, division is a shorthand for subtraction, which is another way to look at addition.
GCD means that what is the biggest number that \(a\) and \(b\) commonly made up of? Let the GCD be \(k\).
Then it means that their difference is also made up of \(k\). That means a linear combination (with integer weights) is also made up of \(k\). They are all in their \(k\) world.
That means when one is divided by the other, their remainer is also made up of \(k\).
Look at it another way.
\(a=b*q+r\)
where \(q\) is the quotient, and \(r\) is the remainder.
Since \(a\) and \(b\) both are divisible by \(k\), \(r=b*q-a\) must also be divisible by \(k\)
As always, we should and we must start with some simple examples with actual numbers. For example, 15 and 9.
def gcd(a,b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
Just for reference, the iterative version of GCD is below. It is brute force and not as clever as the recursive method. But it works.
# iterative
def gcd(a,b):
c = min(a, b)
for i in range(c,0, -1):
print(i)
if (a % i == 0) and (b % i == 0):
return i
print(gcd(9, 15))
Depth-first search (DFS)
DFS is a graph traversal method: for a given graph G, we start at a node N, for each of its children, left to right, we go down as much as possible before going to siblings. In other words, if can go down, go down. Only when cannot go down any further, go right. When cannot go right any more, go up.
def dfs(G, N, visited): # with the visited parameter for recursion
'''
G is represented using adjacency list
'''
if N not in visited:
visited.append(N)
for i in G(N):
dfs(G, i, visited)
return visited
Recipe for recursion
After working out the two simple examples successfully, we can use the same thinking process to tackle bigger recursion problems.
- Write down the mathematical formula of recursion
- Specify initial values correctly
- Code it accordingly. Pay close attention to function inputs, which takes last function call’s output.
Our recipe creation process feels like some kind of recursion too: we came up with a process (or a pattern of a process) that works and generalize it to future ones.
Maybe history is a recursion as well…
Mathematical induction
Mathematical induction is a twin sister of recursion.
If something is true for the initial value of a sequence, And if we can prove that it is true for \(n+1\) if assuming it is true for \(n\), then it is true for all \(n\).
Search binary search tree
Below code searches if a given value is in a binary search tree.
What it does:
- if taget is not found or is equal to the data that is in the current node, then return the current tree (initial value)
- else if target is less than current nodde, then search the left child subtree
- otherwise (if target is greater than current nodde) search the right child subtree
def search(tree, target):
return (tree if not tree or tree.data == target else search(tree, left, target) if target < tree.data else search(tree.right, target))
When to use or not to use recursion
Mathematically we don’t see any reason why not to use it: it is elegant.
Sometimes, such as binary search trees, it is much faster and easy to code using recursion than otherwise.
However in computer implementation, most programs typically do not start any computation until all the recursions have unwind until the base/initial case.
For most languages, unless the language specifically has optmized recursions, the repeated stack calls mean as many stack calls as needed to reach the initial case, which can be quite slow in comparison with some other algorithms such as loops that are optimized in many languages. In addition, the computer may run out of memory because of (millions of) function calls.