Recursion

What is Recursion?

Within Computer Science, which covers algorithms, programming, data, networks, hardware and safe, responsible use of technology, this topic explains Recursion. Computing topics explain how software, hardware and data work, with diagrams and models that show each step in order.

Check that you can explain Recursion in your own words and give one example from everyday life. If you can do that, you have understood the core idea.

Understanding Recursion helps you design, test and explain programs, websites and systems, from small projects to exam questions.

Recursion in detail

Recursion is when a function calls itself to solve smaller versions of the same problem. Every recursive function needs a base case, which stops the recursion, and a recursive case, which moves toward it. For example, factorial(n) = n × factorial(n − 1) with factorial(0) = 1.

Recursion suits problems with self-similar structure such as the Fibonacci numbers, searching trees, the Towers of Hanoi and merge sort. Without a base case, the calls continue until the stack overflows. Recursion can be elegant but use more memory than loops. Understanding it means tracing the calls and returns.

How the interactive helps you understand Recursion

Watch the cycle in the interactive. Use any sliders or buttons it offers to change the values and see how the cycle responds.

Before you change anything, predict the result. Then change one value at a time and check whether your prediction was right. This is a quick way to build a correct mental model of Recursion.

Real-life uses and examples

• Trace through a process that uses Recursion to check what it does step by step.
• Recognise Recursion in an app or device you use every day.
• Apply Recursion when you design a small program, website or spreadsheet.

Common mistakes to avoid

• Testing only the normal case and forgetting the edge cases.
• Using the term without being able to say what the computer actually does.
• Learning the definition without testing it. Use the quiz and the interactive to check that you can apply the idea.