BeginnerTopic 10 of 104Software & Computing
Recursion
A function calling itself on smaller inputs, requiring a base case.
In depth
A recursive function solves a problem by calling itself on a smaller instance, with a base case to stop. Examples: factorial, Fibonacci, tree traversal, divide and conquer. Each call uses stack space; deep recursion may overflow, and naive Fibonacci is exponential without memoisation.
Key points
- Base case and recursive case
- Tail recursion
- Convert to iteration
Examplefactorial(n)=n×factorial(n-1) with factorial(0)=1.
What is Recursion?
A function calling itself on smaller inputs, requiring a base case.
Why is it important to understand recursion?
Recursion expresses problems that split into smaller copies of themselves, such as trees and divide-and-conquer methods.
What must every recursive function have?
A base case that stops the recursion, and a step that moves toward the base case, otherwise the calls never end.
When should I avoid recursion?
When the depth can be very large, since each call uses stack space, and a loop may be simpler and safer.
How is Recursion used in practice?
Typical applications include walking a folder structure to list all files, computing the factorial of a number for a combinatorics task and evaluating an expression tree in a calculator.
What should I learn before Recursion?
Study "Strings" first (topic 9 of 104 in Software & Computing). It covers the groundwork this topic builds on.
What are the key points of Recursion?
Base case and recursive case. Tail recursion. Convert to iteration.
Can you give an example of Recursion?
factorial(n)=n×factorial(n-1) with factorial(0)=1.
What comes after Recursion?
The next topic is "Debugging", which builds directly on this one.
How difficult is Recursion?
It is classed as Beginner in Software & Computing (topic 10 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.