Recursion compared with iteration

Overview

What tail recursion means, iterative version of the factorial algorithm and why recursion can make a program harder to debug.

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

   Define iteration.

   Model answer

   Iteration is the repetition of a block of statements using a loop. The loop ends when its condition is satisfied.

2. 2

   Give two advantages of recursion over iteration.

   Model answer

   A recursive solution is usually shorter and closer to the mathematical definition of the problem. Recursion also suits data structures such as trees that are defined recursively.

3. 3

   Give two disadvantages of recursion compared with iteration.

   Model answer

   Recursion uses more memory because every unfinished call keeps a stack frame. The overhead of making and returning from calls also makes recursion slower.

4. 4

   Can every recursive algorithm be rewritten iteratively?

   Model answer

   Every recursive algorithm has an iterative equivalent, although a stack may have to be managed by hand. The iterative version is often longer and less clear.

5. 5

   Which uses less memory for calculating a factorial, recursion or iteration?

   Model answer

   Iteration uses less memory because one accumulator variable is reused for every step. Recursion needs one stack frame for every value down to the base case.

6. 6

   Why might a programmer still choose recursion even though it is slower?

   Model answer

   A recursive version can be far easier to read and to prove correct. Development and maintenance time often matter more than a small loss of speed.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.