Haskell CS 421 LogoCS 421 — Programming Languages

Recursion

Synopsis

We will talk about recursion, the second most powerful idea of computer science. We assume you have seen recursion before, as well as proofs by induction. This ties the two concepts together and shows you how to write recursive functions in Haskell, as well as how to make a function tail recursive (and why you might want to).

Before watching the videos, think about these questions for five minutes or so.

  • Did you know that if you take the first nn odd numbers and sum them, that the result is n2n^2 (i.e., Σi=1n2i1=n2\Sigma_{i=1}^n 2i-1 = n^2)? Try to prove this by induction; remember you need a base case (when n=1n=1) and an induction case (when n>1n > 1).
  • In your favorite language, try to write a recursive function that computes n2n^2 in the same way, by summing the first nn 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

Activities

Further Reading

  • There and Back Again     This is a research paper about a hybrid of forward recursion and tail recursion.