INB371 Lecture 5
Recursion is a powerful problem solving strategy. Recursion involves reducing a large problem to smaller
problems of the same form. If we’ve been tasked with distributing 1000000 pieces of junk mail, you
couldn’t possibly doing it yourself. You could use a pyramid scheme, which lets people distribute to
other people, and it keeps going down the chain. Having a function call itself is the principle behind
A simple factorial mathematical function to multiply numbers from 1 to n. You could do it iteratively (in
a for loop). Anything done iteratively can most likely be doing with recursion. If N = 0, the factorial
function will return 1, and if it’s not zero, it will call itself until n reaches 0.
Every time the function is called, a new stack frame is created, and any local variables and parameters
that are defined in our main function is placed in the stack frame. As soon as the function is called in
main, the parameter n gets passed with value 4. Once it reaches Factorial 0, it returns 1 to Factorial(1).
This makes Factorial 1’s sum equal to 1 * 1. That returns 1 to Factorial 2, which the does 2 *1, sends 2 to
factorial 3 which does 3 * 2, which is 6, etc.
One of the problems with recursion is that if the recursion doesn’t stop, it will fill the stack with stack
frames, and cause the program to crash due to running out of memory. When making recursive
functions, you need to find the ‘simplest case’ to make it stop, for factorial that’ll be when n = 0.
Fibonacci Sequence can be used as an example of recursion. If a fertile rabbit produces a new pair of
offspring each month, rabbits become fertile in their second month. Because rabbits never die, and all
rabbits from the previous month are still around, the number of fertile rabbit pairs is the number alive in
the previous month, making the new value the sum of the previous two
SEE CODE ON BLACKBOARD
The calculation of Fibonacci sequence from this code causes the calculation to be extremely slow. This is
due to the fact that using recursive functions for this means you have to make calls to an extremely
large amount of functions, as Fib5 needs Fib4 and Fib3, and Fib4 needs Fib3 and 2, etc. This means that
every level doubles the number of calculations. This means that it has a new efficiency class of O(2n).
This is known as exponential efficiency, as the time taken to complete rises exponentially. Additive Sequences
Fibonacci sequence comes from defining t0 = 0 and t1 = 1. We could model different population growth
functions by changing these numbers. All of them use the same recurrence relation though. This means
we can create a new function AdditiveSequence which has parameters t0, t1, and n. Because t1 in the
second additivesequence call in a recursive stack is t0+t1, you simply pass t0+t1 in the t1 param in the
next call. This essentially makes AdditiveSequence parameters hold the calculations al