Introduction to Recursion

July 5th, 2018

Announcements

​

• HW3 due Monday
• HW3 Party tomorrow at 310 Soda, 2-4 PM
• Midterm is coming soon!
• Start studying!
• Practice midterm exams from previous semesters are available online
• More info next week
• Midterm Project spec

Vee Demo

https://snap.berkeley.edu/snapsource/snap.html#present:Username=jkpvecino&ProjectName=LEC%20-%20Vee%20%2B%20Downup

Downup

https://snap.berkeley.edu/snapsource/snap.html#present:Username=jkpvecino&ProjectName=LEC%20-%20Vee%20%2B%20Downup

Definition of Recursion

An algorithmic technique where a function, in order to accomplish a task, calls itself with some part of the task.

Recursive solutions involve 2 major parts:

• Base case - solves a simple case without making a recursive call
• Recursive case - broken up into three main parts
• Divide the problem into simpler instance(s)
• Invoke the function recursively on the simpler instances
• Combine the solved simpler instances into an answer for the current case

Downup Breakdown

Divide: There’s the first and last word, and the middle words.

Invoke: call downup on all but the last letter of the input word.

​

Combine: Join: the word, the downup of the smaller input word, and the word.

Base

case

​

​

Recur-

sive

case

​

You already know recursion!

Drawing Hands (1948), M.C. Escher

Row Count Demo

Row Count in Snap!

Revisiting Recursion

An algorithmic technique where a function, in order to accomplish a task, calls itself with some part of the task.

Recursive solutions involve 2 major parts:

• Base case - solves a simple case without making a recursive call
• Recursive case - broken up into three main parts
• Divide the problem into simpler instance(s)
• Invoke the function recursively on the simpler instances
• Combine the solved simpler instances into an answer for the current case

Row Count in Snap! - complete breakdown

Base

case

​

Recur-

sive

case

​

Divide: There’s the person name, and there’s the rest of the row behind them.

Invoke: call row count on the rest of the row.

​

Combine: Add 1 for the person name to the solution to “how many are behind them”.

Familiar Recursion

thanks to shutterstock

Problem: Make a tree

​

Base case: Size is really small? Make a leaf instead, or don’t make anything

​

Recursive case: Make some wood (trunk), and make two smaller trees to the left and right

What Do You Think?

1. Recursion is more powerful than iteration and easier to write than iteration
2. Recursion is less powerful than iteration and harder to write than iteration
3. Iteration is more powerful than recursion and easier to write than recursion
4. Iteration is less powerful than recursion and harder to write than recursion

Practice Makes Perfect

Recursion is no more powerful than iteration! Often leads to cleaner and better code though.

Base case: simple, immediately solvable version of the problem.

Recursive case:

• Ask: How can I break this problem up using smaller version(s) of itself?
• Always make sure recursive calls are getting closer to your base case!

“Trust the recursion!”

• Assume that your block works when making a recursive call

Review

• Recursion is the second largest idea about computing in this course
• Works best when the problem is self-similar
• Broken up into two parts
• Base case (simplest case)
• Recursive case (divide, invoke, combine)
• It’s no better than iteration, but often leads to more concise and cleaner code

Citations

This presentation was modified from earlier versions created by Dan Garcia, Steven Traversi, and Yifat Amir.