Chapter 3: Recursion
The chapter introduces recursion’s importance, recommends hands-on ways to learn it, and defines pseudocode.
After this chapter you will be able to
- Recursion as an algorithmic building block. Explain that recursion is a coding technique used in many algorithms and a foundation for later material, including divide and conquer.
- Recursive search through boxes. Explain recursion as a function calling itself, using the nested-box search to describe how the search continues into boxes found inside other boxes.
- Base and recursive cases. Explain the roles of the base case and recursive case, and why a countdown function without a base case runs forever.
- Stack push and pop. Explain how the sticky-note to-do list works as a stack: new items go on top, and only the top item can be read and removed.
- Call Stack Function State. Trace how a function call adds its variables to the call stack, how a nested call is placed on top, and how returning removes the top call so the caller resumes where it stopped.
- Separate recursive call state. Explain that each recursive call to fact has its own x, and that the topmost stack entry identifies the call currently running.
- Stack of unfinished searches. Explain how the recursive box search keeps track of boxes still to be searched without an explicit pile.
- Recursive Function Cases. Explain that recursion is a function calling itself and that every recursive function has a base case and a recursive case.
- Stack Operations and Calls. State that a stack has push and pop operations and that all function calls go onto the call stack.
What it builds on
- Arrays and linked lists (chapter 2) · The earlier discussion of arrays and linked lists provides a contrast with a stack’s restricted actions.
Section by section
Introduction
The chapter introduces recursion’s importance, recommends hands-on ways to learn it, and defines pseudocode.
- Recursion as an algorithmic building block: Explain that recursion is a coding technique used in many algorithms and a foundation for later material, including divide and conquer.
Why it matters: This gives you a reason to learn recursion before tackling later algorithms. - Hands-on recursion walkthrough: Describe the suggested ways to learn from the chapter’s recursive code examples: run the code and step through a recursive function with pen and paper.
Why it matters: Following actual calls can make the code examples easier to understand. - Pseudocode as human-readable code: Describe pseudocode as a high-level, code-like description of the problem that is closer to human speech.
Why it matters: Recognizing pseudocode helps you read the chapter’s code-like explanations without treating them as ordinary program listings.
Key terms: recursion, divide-and-conquer strategy, recursive functions, factorial, pseudocode
3.1 Recursion
The section introduces recursion through a search for a key in nested boxes and compares it with a loop-based approach.
- Recursive search through boxes: Explain recursion as a function calling itself, using the nested-box search to describe how the search continues into boxes found inside other boxes.
Why it matters: The box example gives you a concrete way to recognize a function calling itself. - Recursion and loop tradeoff: Distinguish the loop-based pile of boxes from the recursive approach, and explain why the section might favor recursion despite no performance benefit.
Why it matters: Choosing recursion here is about clarity rather than a speed advantage.
Key terms: recursion, function calls itself, while loop, pile, performance
3.2 Base case and recursive case
This section explains why a recursive function needs a base case to stop calling itself.
- Base and recursive cases: Explain the roles of the base case and recursive case, and why a countdown function without a base case runs forever.
Why it matters: A stopping case keeps a recursive function from calling itself forever.
Key terms: base case, recursive case, infinite loop
3.3 The stack
The section introduces a stack through a sticky-note to-do list, explaining how push and pop operate at its top.
- Stack push and pop: Explain how the sticky-note to-do list works as a stack: new items go on top, and only the top item can be read and removed.
Why it matters: This gives you the stack behavior needed to understand the call stack in the next section.
Key terms: stack, push, pop
3.4 The call stack
Explains how the call stack stores each function call’s variables and lets a paused caller resume after another function returns.
- Call Stack Function State: Trace how a function call adds its variables to the call stack, how a nested call is placed on top, and how returning removes the top call so the caller resumes where it stopped.
Why it matters: It explains how a function can call another function without losing its place or its variable values.
Key terms: call stack, function call, variables
3.5 The call stack with recursion
This section uses factorial and a box-search example to show how recursive calls use the call stack to preserve unfinished work, and why that convenience costs memory.
- Separate recursive call state: Explain that each recursive call to fact has its own x, and that the topmost stack entry identifies the call currently running.
Why it matters: Separate call state helps explain how several calls to the same function can be unfinished at once. - Stack of unfinished searches: Explain how the recursive box search keeps track of boxes still to be searched without an explicit pile.
Why it matters: This shows where the work left to do is stored in a recursive search. - Recursive stack memory cost: Explain why many recursive calls use memory and what alternative the section gives when the stack becomes too tall.
Why it matters: The stack saves bookkeeping, but a long chain of calls has a memory cost.
Key terms: call stack, fact, x, pile of boxes, half-completed function calls, memory, stack, loop, tail recursion
3.6 Recap
Recaps recursion’s two cases, stack operations, and how the call stack uses memory.
- Recursive Function Cases: Explain that recursion is a function calling itself and that every recursive function has a base case and a recursive case.
Why it matters: These are the defining features to recognize when describing a recursive function. - Stack Operations and Calls: State that a stack has push and pop operations and that all function calls go onto the call stack.
Why it matters: The call stack connects the idea of a stack to what happens when functions are called. - Call Stack Memory Cost: Explain that a call stack can grow very large and consequently take up a lot of memory.
Why it matters: It identifies a resource cost of a growing call stack.
Key terms: recursion, base case, recursive case, stack, push, pop, call stack, memory
Where this is used later
- Divide and conquer (chapter 4) · Divide and conquer builds on the recursion concepts introduced in this chapter.
- (chapter intro) (chapter 4) · Introduces recursion, which this section identifies as the basis for divide and conquer.
- Quicksort (chapter 4) · The distinction between a base case and a recursive case.
- Queues (chapter 6) · The contrast assumes familiarity with a stack.
- Recap (chapter 6) · Assumes the earlier distinction between stacks and other ways of ordering items.
- Average case vs. worst case (chapter 4) · Recursive calls build up a call stack.
Concepts explained in this chapter
- recursionRecursion is a problem-solving technique in which a procedure solves a problem by invoking itself on smaller or simpler instances of that problem.
- execution context stackA call stack is a runtime stack that stores information for active function calls, including their execution state and local data.
- stopping criterionA base case is the terminating condition of a recursive definition or function that can be solved without another recursive invocation.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.