Recursion: Concepts and Implementation — Topics & Learning Outcomes

Module Topics

What is Recursion?

• 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.

Base Cases and Recursive Cases

• 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.

The Call Stack and Recursion

• 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.

Implementing Factorial with Recursion

• 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.

Fibonacci Sequence Using Recursion

• 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.

Recursive List Traversal

• 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.

When to Use Recursion

• 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)