Computer Science
Grade 9
20 min
Recursive Algorithms
Recursive Algorithms
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Define recursion and its core components.
Identify the base case and the recursive step in a given algorithm.
Trace the execution of a simple recursive function using the concept of the call stack.
Write a basic recursive function in a programming language to solve a problem like calculating a factorial.
Explain the cause of a stack overflow error in the context of infinite recursion.
Compare and contrast a recursive solution with an iterative (loop-based) solution for the same problem.
Have you ever seen a picture of a person holding a picture of themselves, holding a picture of themselves? 🪆 That's the core idea of recursion!
In this tutorial, you will learn about recursive algorithms, a powerful problem-solving technique where a function calls i...
2
Key Concepts & Vocabulary
TermDefinitionExample
RecursionA programming technique where a function calls itself in order to solve a problem.A function `countdown(n)` prints `n` and then calls `countdown(n-1)` until it reaches zero.
Base CaseThe condition within a recursive function that stops the recursion. It represents the simplest version of the problem that can be solved directly.In a `countdown(n)` function, the base case is `if (n <= 0)`, which stops the function from calling itself again.
Recursive Step (or Recursive Case)The part of the function that performs an action and then calls itself with a modified input, bringing it closer to the base case.In a `countdown(n)` function, the recursive step is `print(n)` followed by the call `countdown(n-1)`.
Call StackA data structure used by the computer to keep...
3
Core Syntax & Patterns
The Two Laws of Recursion
1. Must have a base case. 2. Must change its state and move toward the base case.
Every recursive algorithm you write must follow these two rules. The base case prevents infinite loops, and the recursive step ensures the problem is actually being solved and making progress.
Recursive Function Structure
function recursiveFunction(input) {
if (base case is met) {
return base_value;
} else {
// modify input
return recursiveFunction(modified_input);
}
}
This is a standard template for building a recursive function. It clearly separates the base case logic from the recursive step, making the code easier to read and debug.
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
A recursive function is defined as: `function mystery(n) { if (n <= 0) { return 1; } else { return 2 * mystery(n-1); } }`. What is the value returned by `mystery(3)`?
A.6
B.8
C.16
D.7
Challenging
Some recursive algorithms, like one for Fibonacci numbers, may have two base cases (e.g., for n=0 and n=1). Why would a recursive function ever need more than one base case?
A.When the recursive step depends on two or more previous states.
B.To make the code longer and more readable.
C.It is a rule that all complex algorithms must have two base cases.
D.To handle both positive and negative inputs.
Challenging
When comparing a recursive `factorial(n)` function to an iterative (loop-based) one, what is the most significant disadvantage of the recursive approach when `n` is a very large number (e.g., 10,000)?
A.The recursive code is harder to write.
B.The iterative solution is less elegant.
C.The recursive solution consumes a large amount of memory on the call stack, likely causing a stack overflow.
D.The recursive solution will be significantly faster due to modern computer architecture.
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing Free