Recursion

Recursive solutions to problems are typically contrasted with iterative solutions to problems. In a recursive solution, a function (or set of functions) repeatedly invokes slightly modified instances of itself, with each subsequent instance tending closer and closer to a base case. In the meantime, the intermediate calls are all left waiting, having “passed the buck” to a downstream call to give it the answer that it needs. Recursive procedures, when contrasted with iterative ones, can sometimes lead to incredibly efficient, elegant, and even beautiful solutions. Even so, recursion is not often required in CS50 AP.

• Lecture

  • Watch on Youtube
  • Watch on the CS50 Video Player
  • Download Lecture
  • Lecture Notes

• Shorts

  • Recursion
  • Recursion (Zamyla)

• Notes

  • Recursion

• Supplementary Resources

  • Khan Academy on Recursion
  • Stack Overflow discussion on What is recursion and when should I use it?

• Thought Questions

  • Why use recursion at all when you could use loops instead?
  • How would you implement a program that counts from 1 to 10, printing out each number, without using loops?
  • Where do you see recursion in the real world? How could you use recursion to help you solve some problem in your daily life?