×
Computer Science Algorithms

Using Recursion

A common way to approach writing a function is to first handle an easy "base" case, and then transform a problem into a slightly easier problem such that you always arrive at the base case you had already solved.

Here's a simple real-world example:

Imagine you're walking up stairs and want to always know how many stairs you have climbed. You wouldn't get to each stair, look behind you, and count all of the stairs. Doing this several times would be quite annoying. Instead, you would know that climbing each additional stair adds one to the number of stairs you had climbed before, and iteratively keep track of how many stairs you have climbed after each step.

This idea, called recursion, makes for very elegant, efficient code.

Fill in the recursive step in this function, and then use your code to evaluate $$10!.$$

Hint: Remember the definition of factorials and use it to relate $$n!$$ and $$(n-1)!.$$ In the code, you will relate factorial(n) and factorial(n-1).

def factorial(n):
# Solve the base case
if n == 0 or n == 1:
return 1

else:
return # How can you reduce this problem?

print(factorial(10))
Python 3

Recall that the Fibonacci numbers follow the recursion $$F_n=F_{n−1}+F_{n−2}$$ with the initial condition that $$F_1=F_2=1.$$ Fill in recursive step in the code outline provided and use it to calculate $$F_{10}.$$

def fibonacci(n):
if n == 1 or n == 2:
return 1

else:
return #?

print(fibonacci(10))
Python 3

We can now ask ourselves how many arithmetic operations (defined as a single addition, subtraction, multiplication, or division) our solution requires. For factorial 0 operations are required if the input is 1. For inputs greater than 1, we require one more operation than the number of opertions required for $$n−1.$$ Inducting, this means that we need $$n−1$$ operations to compute factorial(n).

How many addition operations are required to calculate fibonacci(10)?. You may find the code template helpful in answering this question.

def num_operations_fibonacci(n):
if n in [1, 2]:
return 0

else:
return #?

print(num_operations_fibonacci(10))
Python 3

Feel free to play around in the previous problem with the number of operations it takes to calculate various Fibonacci numbers. For example, it takes 102334154 operations to calculate the 40th Fibonacci number.

A good approximation for the number of operations it takes to calculate the $$n$$th Fibonacci number is $\frac{1}{2}\left(\frac{1+\sqrt{5}}{2}\right)^n,$ which suggests that it would take approximately $$4.8×10^{208}$$ addition operations to calculate the 1000th Fibonacci number.

Suppose you have a super-computer that can do $$10^{15}$$ additions per second (which corresponds to the current state of the art). How long would it take for your super-computer to calculate $$F_{1000}?$$

This algorithm for calculating the $$n^\text{th}$$ Fibonacci number is prohibitively expensive! This comes to show that even algorithms that look reasonable at first might be really, really bad ideas.

Consider now a different algorithm called smart_fibonacci. How many additions are necessary to calculate the $$F_{1001}$$?

def smart_fibonacci(n):
a, b = 0, 1
for i in range(1,n):
a, b = b, a+b
return b

print(smart_fibonacci(1000))
Python 3

×