Recursion and the base case

Overview

Base case, two essential parts of any recursive definition and what is meant by the depth of recursion.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is recursion?

   Model answer

   Recursion is a technique in which a subprogram calls itself to solve a smaller version of the same problem. Each call works on a simpler case than the one before.

2. 2

   What is a base case, and why must a recursive subprogram have one?

   Model answer

   A base case is a condition that returns an answer without any further call. Without a base case the recursion never stops and the program crashes.

3. 3

   State the two essential parts of any recursive definition.

   Model answer

   A recursive definition needs a base case that stops the recursion. A recursive case then calls the subprogram on a smaller problem.

4. 4

   What happens if the recursive case never moves towards the base case?

   Model answer

   The subprogram calls itself for ever and the call stack fills. The program halts with a stack overflow error.

5. 5

   Give the recursive definition of the factorial of a positive integer n.

   Model answer

   The factorial of 0 is defined as 1. The factorial of n is n multiplied by the factorial of n − 1.

6. 6

   Why is a recursive solution often described as elegant?

   Model answer

   A recursive solution expresses the problem almost exactly as it is defined mathematically. The code is short and its intention is clear.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.