Lesson 1.1
Base Cases
A base case stops the recursion. It must be reachable from every possible call, which is a stronger requirement than merely existing.
Lessons and exercises
Solving a problem by defining a smaller version of itself. The unit is less about writing recursive code than about arguing that it terminates and that the recursive step actually covers the problem.
Lesson 1.2
The Call Stack
Each pending call occupies a stack frame, so recursion depth costs memory even when the code looks small.
Lesson 1.3
Recursive Correctness
A recursive method is argued correct by assuming the recursive call works on a smaller input and showing the combination step is right.
Lesson 1.4
Recursion Versus Iteration
Some problems are naturally recursive because their structure is recursive, such as trees. Others are clearer as loops.
Need help with this topic?
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic