Class 10: Loops reloaded -- Recursion

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"

Recursion

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):

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:

• Think about one step somewhere in the middle of your computation.
• Pretend like all the rest of the steps will just work!
• Write the smallest "base case".

An example:

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

Here's the thought process:

• At some point I'll have to multiply a number, \(n\), by the next smallest number \(n-1\).
• If I can just trust that \((n-1)!\) will work then I only have to do one multiplication.
• A base case is \(1! == 1\) or even \(0! == 1\)

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.