1.4 Recursion Versus Iteration | Code Scholars Tutoring

How it works

Some problems are naturally recursive because their structure is recursive, such as trees. Others are clearer as loops.

Choose recursion where the data is self-similar and iteration where progress is linear.

Common error

Forcing recursion onto a simple accumulation, which adds stack cost for no clarity.

Worked example

Java snippets run inside a main method. Add import java.util.*; when collection types are used.

Java

int sum = 0;
for (int n = 4; n > 0; n--) sum += n;
System.out.println(sum);

Output

This iterative sum and the simple recursive sum both use linear time. The iterative version uses constant auxiliary storage, while the direct recursive version uses a linear-depth call stack.

Exercises

1.4.1 · Explain

Compare auxiliary space for a simple depth-n recursive factorial and a loop-based factorial.

Show solution

The direct recursion uses O(n) call-stack space. The loop uses O(1) auxiliary space under a fixed-width arithmetic model.

1.4.2 · Write code

Implement an iterative factorial for n = 5.

Show solution

Accumulate a product starting at 1.

One valid solution

long product = 1;
for (int n = 2; n <= 5; n++) product *= n;
System.out.println(product);

Expected output

Open Java compiler