QUESTION 43 · Recursion

How do recursion and iteration repeat work?

2 marks

Answer

Recursion repeats through function calls; iteration repeats through loops.

Recursion needs a base case and progress towards it.
A loop needs a suitable stopping condition and progress towards it.

Compare recursion and iteration with reference to factorial.

5 marks

Answer in brief

Recursion solves repeated work through calls to smaller problems. Iteration performs repeated work using a loop.

Recursion

Recursive factorial returns 1 at its base case and otherwise returns n × factorial(n - 1). Each active call waits for the smaller result. The definition closely follows the mathematical relationship. With n levels it takes O(n) time and O(n) auxiliary space in the usual call-record model.

Iteration

Iterative factorial starts result at 1 and multiplies it by each value from 2 through n. There is no chain of pending recursive calls. It also takes O(n) time, because the number of multiplications grows linearly. Only a counter and result are needed, giving O(1) auxiliary space.

Comparison

Stopping: recursion uses a base case; iteration uses a loop condition or an explicit exit.
Stored state: recursion can keep separate state in active calls; iteration uses explicit variables.
Readability: recursive problems such as tree traversal may be easier to describe recursively.
Limits: deep recursion can exhaust call resources; a loop can still be wrong or non-terminating if its progress rule is faulty.

Which should be chosen?

For a simple factorial, iteration usually avoids unnecessary call depth. For naturally recursive structures, recursion can be clearer. Neither form is always faster or always better. Count the actual work and stored state. C does not guarantee tail-call optimisation, so it cannot be assumed to reduce every recursive function to constant extra space.

Correctness

Both forms must handle 0! = 1, reject unsupported negative input and avoid overflowing the result type. Changing recursion to a loop does not remove arithmetic limits.

Comparison table

↔ Scroll horizontally on a small screen

Factorial: recursion and iteration
Feature	Recursion	Iteration
Repetition	Smaller function calls	Loop iterations
Stopping	Base case	Loop condition
Time	O(n)	O(n)
Auxiliary space	O(n) active calls	O(1) variables