Recursions
Considering the example of computing factorial, which can be defined as: n! = n.(n-1).(n-2)….3.2.1
There are many ways to calculate facotrial of a number, one way is by first computing (n-1)! and multiplying the result by n on the condition that 1! is 1.
def factorial(n):
if n == 1:
return 1
else:
return (n * (factorial(n-1)))
Now we can compute factorial using a different perspective.We can compute n! by specifying that we frst multiply 1 by 2, then multiply the result by 3,then by 4 and so on until we reach n. In this process,we maintain a running product,together with a counter that counts from 1 to n.Thus the computation can be described as:
product <- counter * product
counter <-counter + 1
def fact_iter(product,counter,max_count):
if counter > max_count:
return product
else:
return fact_iter(product * counter,counter + 1,max_count)
def factorial(n):
res = fact_iter(1,1,n)
return res
To study the difference between the two techniques, let’s use the substitution model to see the calling structure:
This is for the first technique
factorial(6)
( 6 * factorial(5))
( 6 * (5 * factorial(4)))
( 6 * (5 * (4 * factorial(3)))))
( 6 * (5 * (4 * (3 * factorial(2)))))
( 6 * (5 * (4 (3 *(2 * factorial(1))))))
( 6 * (5 * (4 (3 *(2 * 1))))
( 6 * (5 * (4 (3 * 2))))
( 6 * (5 * (4 * 6)))
( 6 * (5 * 24))
( 6 * 120)
(720)
Now the call structure for the second one looks as:
factorial(6)
(fact_iter(1,1,6))
(fact_iter(1,2,6))
(fact_iter(2,3,6))
(fact_iter(6,4,6))
(fact_iter(24,5,6))
(fact_iter(120,6,6))
(fact_iter(720,7,6))
720
Considering the first process:
- The substitution model reveals a shape of expansion followed by contraction.
- The expansion process ocurrss due to the chain of deferred operations.
- While the contraction ocurrs as the operation are actually performed.
- Carrying out such operations, the interpreter needs to keep track of the operations to performed later on and this grows linearly with n.
- This process is called linear recursion
Now the second process:
- This does not have to grow or shrink.
- At each step,we need to keep track of, for any n, the current values of product,counter and max_count.
- Such a process is called an iterative process as the state can be summarized by a fixed number of state variables.
- In computing n!, the number of steps grow linearly with n, such a process is called a linear iterative process.
Tree Recursion
An alternative pattern for recusrion is tree recursion.For example let’s consdier computing the sequence of Fibonacci numbers, in which each number is the sum of the preceeding two:
0,1,1,2,3,5,8,13,21....
which can be represented as fib(n) = fib(n-1) + fib(n-2),if n=0, fib(n)=0 and if n=1, fib(n)=1.
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return (fib(n-1) + fib(n-2))
Usage:
for n in range(0,5):
print(fib(n))
To compute fib(5),we have to compute fib(4) and fib(3).To compute fib(4), we compute fib(3) and fib(2). The whole process will evolve into a tree like structure:
fib(5)
/ \
/ \
/ \
/ \
fib(4) fib(3)
/ \ / \
/ \ / \
/ \ fib(2) fib(1)
fib(3) fib(2) / \ |
/ \ / \ / \ 1
/ \ / \ fib(1) fib(0)
/ \ fib(1) fib(0) | |
fib(2) fib(1) | | 1 0
/ \ | 1 0
/ \ 1
/ \
fib(1) fib(0)
| |
1 0
By looking into the tree structure we can see that almost half the work gets duplicated.The process uses a number of steps that grows exponentially with the input or specifically to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.If the inputs are numbers, tree recursion is less efficient on the other hand for processes that operate on hierarchical data structures,tree recursion is a powerful tool. The above process can be converted into a Linear iteration The idea is to use a pair of integers to repeatidly apply the simultaneous operation:
a is initialized to fib(1)=1
b is initialized to fib(0)=0
a <- a + b
b <- a
Implementation
def fib(n):
fib_iter(1,0,n)
def fib_iter(a,b,count):
if count == 0:
return b
else:
count = count - 1
print(f'a {a},b {b} count {count}')
return (fib_iter((a+b),a,count))
There are some more examples on recursions that I am working and will update this post soon.