Announcements (#1)

Come to office hours! (Not just for this class but your other classes, too)

• Any questions welcome, especially non-lab, non-proj questions (but those are fine, too).
• Also available by appointment. Send me an email.
• Monday hours and place have moved:
• Now: 1:20 - 2:10 at the Wozniak Lounge courtyard, outside Soda hall.

Announcements (#2)

The algorithmic complexity lecture was pretty intense!

• Intended as a brief introduction to a topic you’ll maybe one day spend much much more time on in 61B.
• Don’t worry if that lecture felt particularly hard.
• Most clicker questions had < 30% accuracy from classmates!

Announcements (#3)

Road map of the coming two weeks:

• Three difficult assignments due over the next 12 days: Recursion labs and project 3.

Tricky lectures.

Hard lab.

Hard project.

Tricky lecture.

Hard lab.

Hard lab.

P.S. Let’s do a website tour.

CS10: The Beauty and Joy of Computing - Fall 2021

Lecture 9: Recursion I

• Intro to Recursion
• Solving Problems Using Recursion
• Tree Recursion

Puzzle

What does the ulgometh command do?

• Assume x is a number.

​

​

​

​

​

​

If you’re not sure where to start consider:

​

Puzzle #2

How would we modify ulgometh so that it stops at 0?

• Last thing it should say is 0.
• You’re not allowed to use loops!

Recursion

Recursive (adjective): A procedure is called recursive if the body of the procedure calls the procedure itself.

​

Recursion is just the noun version of recursive.

Recursion

Alternate approach on the right.

• The two programs below are EXACTLY identical in behavior.
• For left version, with no else, there was no need to call “stop” explicitly.
• Just like any block, when ulgometh runs out of things to do, it stops automatically.

Recursion

In its most boring form, recursion is simply an alternative to looping (a.k.a. iteration).

• Anything you can do with a loop, you can do with recursion (and vice versa)

​

However, it is also a profoundly powerful way of thinking!

• Recursion adds no additional power to Snap!, but will make certain things much easier.
• Think of recursion as another tool. Not mandatory, but often useful.

​

List of algorithmic elements: https://docs.google.com/presentation/d/1Xmm6iYL7MtIQIJ1JXHqDy8kdMVAejViRfH5swfLbNJ4/edit#slide=id.gebdf3f01da_0_196

We’ve Used Recursion Before

Used this idea implicitly in the way we described selection sort.

• Find smallest, move that to that front.
• Repeat this entire procedure, but for every item in the list except the first.

To selection sort this list...

Move 1 to the front:

Then selection sort this list...

Solving Problems Using Recursion

List Concatenation

Consider a command “add everything in ___ to ___”:

• Example, the code below would add everything in [X, Y, Z] to the end of [a, b, c], resulting in the list [a, b, c, X, Y, Z]

​

​

​

Would map, combine, or keep be useful for this task?�

List Concatenation

Consider a command “add everything in ___ to ___”:

• Example, the code below would add everything in [X, Y, Z] to the end of [a, b, c], resulting in the list [a, b, c, X, Y, Z]

​

​

​

Would map, combine, or keep be useful for this task?

• No. Map gives yields a list of same length as its argument. Combine yields a single value. Keep yield a subset of the items in a list. Also none of these modify an existing list (they are reporters).

​

We could do this with a loop, but let’s use recursion.�

Examples of Recursion

Implement the “add everything in __ to __” command using the 8 blocks below.

• You may not need all blocks provided.
• Hint: Ulgometh had nothing to do when x < 0. Add everything has nothing to do when new stuff list is empty.

​

​

Solution Debrief

Deconstructing Josh’s Solution

Like almost all recursive code, solution is divided into two pieces:

• The base case: What happens for any special inputs. In this example, if the “new stuff list” is empty, there’s nothing to do, so we don’t do anything.
• The recursive case:
• You add the first thing from “new stuff list.”
• Then you add everything else (using a recursive call!!)

Treating a recursive call as a usable abstraction is often called a “Recursive Leap of Faith”

Alternate Implementation

An arguably simpler version is shown below.

• Difference is that the “base case” is like a trap: If the special base case occurs, this call to “add everything in ___ to ___” gets stopped.
• If you don’t fall into the trap, you just keep going.

Acts like a “report” in the sense that code stops running.

If you use this approach make sure to use “stop this block”, not “stop this script”.

Another Example: Downup (time permitting)

Let’s implement a recursive reporter.

• Very contrived example! There’s probably no reason you’d actually want a reporter that does.

​

​

Another Example: Downup (Solution)

We’ll get a lot more practice with recursive reporters during next week’s Monday lecture and the recursive reporter lab.

​

​

​

​

​

​

​

This way of programming is very challenging to learn.

• Some of the trickiest problems you do in 61A or 61B will feel like this.

​

​

The Towers of Hanoi

One Last Example: The Towers of Hanoi

Sometimes the recursive leap of faith feels like magic.

​

“In the great temple at Benares beneath the dome which marks the center of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four disks of pure gold, the largest disk resting on the brass plate and the others getting smaller and smaller up to the top one. This is the Tower of Brahma. Day and night unceasingly, the priests transfer the disks from one diamond needle to another according to the fixed and immutable laws of Brahma, which require that the priest on duty must not move more than one disk at a time and that he must place this disk on a needle so that there is no smaller disk below it. When all the sixty-four disks shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish. “ (Henri de Parville, 1883 (see Orientalism))

Problem and Animated Solution (watch later if you want)

Basic idea:

• Can only move one disk at a time.
• A larger disk can NEVER sit on top of a smaller one.
• Only three pegs available for movement.
• Goal is to get entire stack from leftmost peg to the rightmost peg.

Let’s try this out interactively: http://towersofhanoi.info/Play.aspx

Solving the Towers of Hanoi

There is a very simple recursive solution.

• So simple it is confusing to understand!
• I do NOT expect you to understand this fully today.
• It may be until you take 61A or work as an academic intern for this course that you finally actually understand this.

​

​

Solving the Towers of Hanoi (Recursive Solution)

To Move N Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top N-1 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top N-1 disks from temp needle to destination�

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 5 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 4 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 4 disks from temp needle to destination�

Source

Destination

temp

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 5 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 4 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 4 disks from temp needle to destination�

Source

Destination

temp

Key tricky point: For moving 4 disks, we’ll use the ‘source’ as the temp, and the ‘temp’ as the source.

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 5 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 4 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 4 disks from temp needle to destination�

Source

Destination

temp

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 5 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 4 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 4 disks from temp needle to destination�

Source

Destination

temp

See extra slides for a slightly more thorough animation.

Test Your Understanding

Suppose we had a block called:

​

​

​

​

If we called this block with N = 3, s = LEFT, d = MIDDLE, temp = RIGHT, what would happen?

Another Way of Putting It...

Suppose we had a block called:

​

​

​

​

If we called this block with N = 3, s = LEFT, d = MIDDLE, temp = RIGHT, what would happen?

Another Way of Putting It...

Suppose we had a block called:

​

​

​

​

If we called this block with N = 2, s = MIDDLE, d = LEFT, temp = RIGHT, what would happen?

Another Way of Putting It...

Suppose we had a block called:

​

​

​

​

If we called this block with N = 2, s = MIDDLE, d = LEFT, temp = RIGHT, what would happen?

Another Way of Putting It...

Suppose we had a block called:

​

​

​

​

If we wanted to solve the puzzle using the block above, what would we pick for N, s, d, and temp?

Another Way of Putting It...

Suppose we had a block called:

​

​

​

​

If we wanted to solve the puzzle using the block above, what would we pick for N, s, d, and temp?

• N=5
• s=LEFT
• d=RIGHT
• temp=MIDDLE

Let’s Try This Out in Snap!

This is going to hurt your brain.

• … but it really works!
• A single call to the function below solves the puzzle.

​

​

• So now all we need to do is write the move top disks block. The recursive leap of faith tells us that as long as this block works, it works.

​

https://snap.berkeley.edu/project?user=joshhug&project=cs10_fa21_lec9_hanoi

​

Again: I do not expect you to deeply understand the 4 line solution.

• However, I do want you to have a sense of awe at this solution.

Let’s Try This Out in Snap!

This is going to hurt your brain.

• … but it really works!
• A single call to the function below solves the puzzle.

​

​

• So now all we need to do is write the move top disks block. The recursive leap of faith tells us that as long as this block works, it works.

Starter code:

https://snap.berkeley.edu/project?user=joshhug&project=cs10_fa21_lec9_hanoi

Solution:

https://snap.berkeley.edu/project?user=joshhug&project=cs10_fa21_lec9_hanoi_complete

​

Closing Thoughts

Recursion adds no additional power to Snap! language.

• Anything that can be done with loops can be done with recursion (and vice-versa).
• Your recursive programs should always have base case and recursive case.
• Makes some things much easier and more elegant.
• Particularly problems with “self-similarity”.
• e.g. Selection sort can be thought of as “moving smallest item to front”, followed by sorting the rest of the list.
• e.g. Fractal/tree like drawings (see next lecture).

​

When working on labs from here on out: Use scratch paper.

• Too much to hold in your brains.

​

Extra Slides: More Verbose Animation of Towers of Hanoi

Solving the Towers of Hanoi

That animation was probably daunting, but the recursive solution is actually very simple.

• So simple it is confusing to understand!

Solving the Towers of Hanoi (Recursive Solution)

To Move N Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top N-1 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top N-1 disks from temp needle to destination�

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 5 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 4 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 4 disks from temp needle to destination�

Source

Destination

temp

For the move top 4 disks call, s = LEFT, d = RIGHT, temp = MIDDLE

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 4 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 3 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 3 disks from temp needle to destination�

Source

temp

Destination

For the move top 3 disks call, s = LEFT, d = MIDDLE, temp = RIGHT

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 4 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 3 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 3 disks from temp needle to destination�

Source

temp

Destination

etc

For the move top 3 disks call, s = LEFT, d = MIDDLE, temp = RIGHT

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 4 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 3 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 3 disks from temp needle to destination�

Source

temp

Destination

For the move top 3 disks call, s = LEFT, d = MIDDLE, temp = RIGHT

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 4 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 3 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 3 disks from temp needle to destination�

Source

temp

Destination

Now back to moving 4 disks.

For the move top 3 disks call, s = LEFT, d = MIDDLE, temp = RIGHT

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 5 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 4 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 4 disks from temp needle to destination�

Source

Destination

temp

Key tricky point: For moving 4 disks, we’ll use the ‘source’ as the temp, and the ‘temp’ as the source.

For the move top 4 disks call, s = LEFT, d = RIGHT, temp = MIDDLE

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 5 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 4 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 4 disks from temp needle to destination�

Source

Destination

temp

For the move top 4 disks call, s = LEFT, d = RIGHT, temp = MIDDLE

Solving the Towers of Hanoi (Recursive Solution Demo).

To Move 5 Disks from source to destination:

• If N=1, just move the disk from source to destination, otherwise:
• Move top 4 disks from source to temp needle
• Move the remaining bottom disk from source to destination
• Move top 4 disks from temp needle to destination�

Source

Destination

temp

For the move top 4 disks call, s = LEFT, d = RIGHT, temp = MIDDLE