Recursion

2016-06-02

We will talk about recursion, the second most powerful idea of computer science. You have likely seen recursion before, as well as proofs by induction. Before watching the videos, think about these questions for five minutes or so.

• Did you know that if you take the first $n$ odd numbers and sum them, that the result is $n^2$ (i.e., $\Sigma_{i=1}^n 2i-1 = n^2$)? Try to prove this by induction; remember you need a base case (when $n=1$) and an induction case (when $n > 1$). Try this even if you have completely forgotten how to do induction.
• In your favorite language, try to write a recursive function that computes $n^2$ in the same way, by summing the first $n$ odd numbers.
• Imagine that you had a recursive function that never made use of the result of its recursive call. Would such a function even be useful? (Hint: the answer is “yes.”) What kinds of things could you do if you could guarantee to the compiler that this would be the case?

Videos

• Induction
• Basic Recursion
• Tail Recursion

Activity

• Activity Due by Monday, June 6, do the convert-to-tail problems.

In Class Examples

• Code
• Shell