Recursive techniques

Overview

Recall questions on base and general cases, what happens when the base case is never reached, the part played by the call stack, and tracing recursive factorial and summation.

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 in programming?

   Model answer

   A technique in which a subroutine calls itself, directly or through another subroutine, to solve a smaller version of the same problem. Each call works on a simpler case until one is reached that can be answered outright, and the answers are then combined back up the chain.

2. 2

   What is the base case of a recursive subroutine?

   Model answer

   The case that can be solved directly without any further recursive call, and which therefore stops the recursion, for example the factorial of 0 being 1 or a list of length 0 summing to 0. It must be tested before any recursive call is made.

3. 3

   What is the general case of a recursive subroutine?

   Model answer

   The case that expresses the answer in terms of the same subroutine applied to a smaller or simpler input, such as the factorial of n being n multiplied by the factorial of n - 1. Every general case must move the problem closer to the base case.

4. 4

   What happens if a recursive subroutine has no base case, or never reaches it?

   Model answer

   It calls itself endlessly. Each call pushes another stack frame, memory is used up, and the program fails with a stack overflow rather than looping harmlessly for ever. This is the recursive equivalent of an infinite loop, and it is why the base case must be reachable from every general case.

5. 5

   Describe the mechanism by which recursion is implemented.

   Model answer

   Every call, including a recursive one, pushes a stack frame holding its return address, its parameters and its local variables, so each level keeps its own separate copy of the values it is working on. Calls pile up on the way down until the base case returns a value without calling again; the frames are then popped one at a time, each level receiving the value returned by the level below, completing its own calculation and returning to the level above, until the original call returns to the caller.

6. 6

   Give the recursive definition of the factorial function.

   Model answer

   The factorial of 0 is 1, which is the base case. For any n greater than 0, the factorial of n is n multiplied by the factorial of n - 1, which is the general case. As pseudo-code: FUNCTION fact(n) IF n = 0 THEN RETURN 1 ELSE RETURN n * fact(n - 1) ENDIF ENDFUNCTION.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.