1. Intro to Recursion #

Created Saturday 28 December 2019

• Recursion: A problem that can be expressed in terms of same problem(itself) but with a smaller input(until an anchor point, obviously).

(Don’t say that a function calls itself, it actually calls a smaller version of itself). e.g. factorial: i.e f(n) = n * f(n-1) , f(0) = 1.

• The anchor point is just a trivial instance of the problem, and the answer is known.
• Recursion works by making a stack of activation records.

**Note: **We don’t have to make manually manage activation records, as this is tedious. We’ll see better representation in the next lecture.

• It’s very intuitive and helpful in solving many problems.
• Many optimal algorithms are recursive.