Don't like this style? Click here to change it! blue.css

Class 10: Loops reloaded -- Recursion

infinite lisa

freaking vortex

M.C. Escher

The tests are graded. This was an answer from one of you which accidently, and recursively, creates a very slow infinite loop:

Loops in review:

Code Review Task 1: Split the following functions up with a small group (ignore the trivial ones). Each person pick 1-2 to fully understand. Then describe the way your function works to the rest of your group. When you are done each person should totally understand each example:

We saw loops that did many types of tasks:

Doing a task a fixed number of times:

Repeating a block of commands in several different contexts:

Repeating until some goal is reached:

Iterating through something (list, string, dictionary):

To accumulate a result:

Loop Task 2: Write a function which consumes a string and returns a string containing only the capital letters from the input string. For instance assert myfunc("Andy Is GrEat") == "AIGE"


We will call a function recursive when it calls itself to finish its task. All loops can be re-written in a recursive way (and all recursive functions can be rewritten in a loop-style). The benefit is not new types of problems you can solve, the benefit is a new way of thinking and problem solving.

Joke Task 3: Google search "recursion".

I don't want you to think of recursion as infinite or "turtles all the way down" (a cosmology reference you'll have to look up):

All the way down

In computer science we typically will solve problems with recursion by making a smaller problem each time.

Analyze Task 4: In this countdown snippet, what line causes the next "loop"/"iteration" to start? Why does this eventually stop executing?

Here is a secret to working with recursive algorithms:

An example:

One of the first examples of a recursive algorithm is computing \(n!\).

Here's the thought process:

Recursive Task 5: Write a recursive function which counts backwards from 100 by 3s and stops at 1.

Recursive Sum Task 6: Write a recursive function to add the numbers 1, 4, 7, …, 100.

Recursive Product Task 7: Write a recursive function to multiply those same numbers.

Euclidean Algorithm

One of the best algorithms of all time is the Euclidean algorithm. It calculates the greatest common divisor of two numbers. For instance the gcd(25, 30) is 5.

The gcd(x, 0) is always x (because everything "divides" 0 since x*0 == 0).

The big observation of Euclid's is that gcd(x, y) == gcd(y, x % y). Which makes a smaller problem.

For example gcd(11,8) is the gcd(8, 3) which is the gcd(3, 2) which is the gcd(2, 1) which is gcd(1, 0) which is 1.

Transcendentally Cool Task 8: Write a recursive GCD function which takes two arguments and returns the biggest number that divides them both. Talk out with your neighbors what the base case is and what the recursive step is.

This is transcendental because the problem and method are older than the English language, and your grandma's grandma. You've just joined a group of thinkers stretching well beyond our culture.

Daily Challenge:

Write a recursive function which calculates the nth fibonacci number (F(n) == F(n-1) + F(n-2) and F(0) == 1, F(1)==1). The pattern is 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …