Recursion
A function calls itself on a smaller version of the problem.
About this topic
Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case, which stops the process, and a recursive case, which moves closer to the base case. Without a base case the function calls itself forever until the program runs out of memory, called a stack overflow.
The classic example is factorial: n factorial equals n times (n minus 1) factorial, with 0 factorial equal to 1. Computing 4 factorial calls 3 factorial, then 2, then 1, then 0, which returns 1, and the results multiply back up to 24. Each call waits on the call stack until the one below finishes. The Fibonacci sequence and the Tower of Hanoi are also naturally recursive.
Recursion is ideal for trees, folders inside folders, and divide and conquer algorithms like merge sort. Anything recursive can also be written with loops, which may be faster and use less memory. A common mistake is forgetting the base case or not shrinking the problem. When designing, first ask what the simplest case is and what the next smaller problem looks like.
Key ideas
- Base case stops it
- Factorial and Fibonacci
- Uses the call stack
Quick check
Use cases: where Recursion helps
- Homework: review the key idea behind Recursion before you start a problem set.
- Exam revision: use the quick check to test whether you can recall Recursion without notes.
- Visual learning: play with the interactive lab to see how Recursion changes when you adjust its inputs.
- Teaching a friend: explain Recursion in your own words, then compare your version with the key ideas.
Computing ideas run phones, search engines, games and the wider internet.
Frequently asked questions
What is Recursion?
A function calls itself on a smaller version of the problem.
What will I learn in Recursion?
Base case stops it. Factorial and Fibonacci. Uses the call stack.
Is Recursion part of Computer Science?
Yes. It is one of 80 Computer Science topics on LearnViz HighSchoolEdu, with 3 key ideas, a live animation and a quick check.
Does the Recursion lab work on a phone or tablet?
Yes. The animation resizes to fit your screen and supports touch, so you can drag, tap and slide with your finger.
How should I study Recursion?
Read the summary and key ideas first, play with the interactive lab to see the idea in motion, then answer the quick check. If you get a question wrong, go back to the key idea it tests.
Do I need an account, and is my progress saved?
No account is needed. Marking a topic as learned is saved in your own browser, so it stays on that device and is not sent to a server.