Recursion: Concepts and Implementation — Topics & Learning Outcomes

Module Topics

1. What is Recursion?

Materials for topic 1 (2)

• Defining Recursion — Recursion is a programming strategy in which a function solves a problem by calling itself as part of its own definition.
• The Self-Referential Nature of Recursive Thinking — Recursion requires thinking about a problem in terms of itself — breaking it into a case that can be handled now and a remainder that looks just like the original problem.
• Recursion vs. Iteration — Recursion and iteration (loops) are two complementary strategies for repeating operations, and many problems can be solved with either approach.
• Why Recursion Matters as a Strategy — Recursion is more than a syntax feature — it is a high-level problem-solving strategy that appears across classic algorithms and data structures.
• The Conceptual Building Blocks of a Recursive Function — Every recursive function relies on two essential conceptual components: a point where it stops, and a step where it calls itself.

2. Base Cases and Recursive Cases

Materials for topic 2 (2)

• What Is a Base Case? — The base case is the condition in a recursive function that stops further recursive calls and returns a direct result.
• What Is a Recursive Case? — The recursive case is the part of the function where it calls itself with a modified argument, moving step by step toward the base case.
• Why Both Components Are Necessary — A correct recursive function requires both a base case and a recursive case working together to produce a result without infinite looping.
• Identifying the Base Case in Classic Algorithms — Recognizing what counts as the simplest, directly solvable version of a problem is the key skill for writing correct base cases.
• Ensuring the Recursive Case Converges — The recursive case must consistently reduce the problem size so that the base case is eventually reached on every valid input.
• Infinite Recursion and Stack Overflow — When a base case is missing or unreachable, the function calls itself without end, eventually exhausting the call stack and causing a runtime error.

3. The Call Stack and Recursion

Materials for topic 3 (2)

• What Is the Call Stack? — The call stack is a data structure the JavaScript runtime uses to track the execution of function calls in a program.
• Stack Frames and Execution Context — Each entry placed onto the call stack is called a stack frame, and it stores all the information needed to execute that particular function call.
• How Recursive Calls Build the Stack — Every recursive function call adds a new stack frame on top of the previous one, causing the stack to grow deeper with each level of recursion.
• Stack Depth and Recursion Depth — Stack depth refers to the number of active stack frames at any given moment, which in a recursive function corresponds directly to how many levels deep the recursion has gone.
• Stack Overflow: When Recursion Goes Too Deep — A stack overflow error occurs when the call stack exceeds its maximum allowed size, typically because recursion has gone too deep without reaching a base case.
• Preventing and Mitigating Stack Overflow — Developers can reduce the risk of stack overflow by carefully designing base cases, limiting input size, or restructuring recursion to use less stack space.

4. Implementing Factorial with Recursion

Materials for topic 4 (2)

• The Mathematical Definition of Factorial — Factorial is a mathematical operation defined recursively: n! equals n multiplied by (n-1)!, with 0! defined as 1.
• Identifying the Base Case — Every recursive factorial function must include a base case that stops the recursion — in this instance, when n equals 0.
• Writing the Recursive Call — The recursive case expresses the problem in terms of a smaller version of itself, mirroring the mathematical rule n! = n × (n-1)!.
• Complete Factorial Function in JavaScript — Combining the base case and the recursive call produces a complete, working factorial function in JavaScript.
• Tracing Execution Through the Call Stack — Tracing how factorial(3) executes step by step reveals how JavaScript manages recursive calls using the call stack.
• Connecting Mathematical Structure to Code Structure — The factorial implementation demonstrates a direct one-to-one correspondence between a mathematical recursive definition and recursive JavaScript code.

5. Fibonacci Sequence Using Recursion

Materials for topic 5 (2)

• What Is the Fibonacci Sequence? — The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1.
• Defining the Base Cases — As with all recursive functions, the Fibonacci implementation requires base cases to stop the recursion from running indefinitely.
• Implementing Fibonacci Recursively in JavaScript — The recursive Fibonacci function in JavaScript directly mirrors the mathematical definition, using two recursive calls in its return statement.
• How the Call Stack Grows with Two Recursive Calls — Because each call to fibonacci() spawns two additional calls, the call stack branches into a tree structure rather than a linear chain.
• Performance Trade-offs of Naive Recursive Fibonacci — The naive recursive implementation of Fibonacci has significant performance drawbacks due to the repeated recalculation of the same subproblems.
• Tracing a Small Fibonacci Example by Hand — Manually tracing through a small Fibonacci call, such as fibonacci(4), helps solidify understanding of how recursive calls expand and resolve.

6. Recursive List Traversal

Materials for topic 6 (2)

• What Is Recursive List Traversal? — Recursive list traversal is the technique of processing each element in a list or array by having a function call itself on a progressively smaller portion of the structure.
• Defining the Base Case for List Traversal — As with all recursive functions, a base case must be defined to stop recursion and prevent infinite loops when traversing a list.
• JavaScript Implementation: Traversing an Array — In JavaScript, recursive list traversal can be implemented by slicing the array to separate the first element from the rest on each call.
• Processing Elements During Traversal — Recursive traversal is not limited to simply visiting each element — it can also accumulate results, transform values, or search for specific items.
• Recursive Thinking vs. Iterative Thinking for Lists — Recursive list traversal encourages a different mental model compared to iterative loops — focusing on 'what to do with one element' rather than 'how to loop through all elements'.
• The Call Stack During List Traversal — Each recursive call to traverse a list adds a new frame to the JavaScript call stack, which holds the current element and the remaining list for that call.

7. When to Use Recursion

Materials for topic 7 (2)

• Recursion vs. Iteration: Core Trade-offs — Recursion and iteration are two fundamental approaches to solving repetitive problems, and choosing between them involves weighing clarity against performance.
• Problem Types Best Suited to Recursion — Certain problem structures map so naturally onto recursion that a recursive solution is significantly easier to design and understand than an iterative one.
• Readability and Code Clarity — One of the strongest arguments for recursion is that it can make code read almost like a direct translation of the problem's definition or mathematical specification.
• Performance Considerations and Pitfalls — Recursion introduces performance costs that must be understood before choosing it, particularly regarding memory usage and redundant computation.
• Practical Guidelines for Choosing Recursion — Selecting recursion over iteration should be a deliberate decision based on the problem's structure, expected input size, and the priorities of the codebase.

Student Learning Outcomes

By the end of this module, students will be able to:

Course Outcomes (reference)

Materials for Each Topic

What has been made for each topic. Materials that cover the whole module are listed on the module page.

1. What is Recursion?

↑ Back to topic 1

• What is Recursion? Topic Detail · Web page
• What is Recursion? — Videos Topic Videos · Web page

2. Base Cases and Recursive Cases

↑ Back to topic 2

• Base Cases and Recursive Cases Topic Detail · Web page
• Base Cases and Recursive Cases — Videos Topic Videos · Web page

3. The Call Stack and Recursion

↑ Back to topic 3

• The Call Stack and Recursion Topic Detail · Web page
• The Call Stack and Recursion — Videos Topic Videos · Web page

4. Implementing Factorial with Recursion

↑ Back to topic 4

• Implementing Factorial with Recursion Topic Detail · Web page
• Implementing Factorial with Recursion — Videos Topic Videos · Web page

5. Fibonacci Sequence Using Recursion

↑ Back to topic 5

• Fibonacci Sequence Using Recursion Topic Detail · Web page
• Fibonacci Sequence Using Recursion — Videos Topic Videos · Web page

6. Recursive List Traversal

↑ Back to topic 6

• Recursive List Traversal Topic Detail · Web page
• Recursive List Traversal — Videos Topic Videos · Web page

7. When to Use Recursion

↑ Back to topic 7

• When to Use Recursion Topic Detail · Web page
• When to Use Recursion — Videos Topic Videos · Web page