Skip to main content

Recursion; iterative vs recursive choice

Short answer

Recursion is a technique where a function calls itself to solve smaller instances of a problem until a base case. Prefer iteration for simple repetitive tasks (factorial, Fibonaci) due to speed and memory; prefer recursion for naturally recursive problems like tree traversal or Tower of Hanoi for clarity.

Define a recursion. Which algorithm would you prefer between iterative and recursion?

Recursion is a technique in which a function calls itself (directly or through another function) to solve a problem by reducing it to smaller instances of the same problem, until a simple base case is reached. Example: fact(n) = n × fact(n-1), fact(0) = 1.

Which is preferred?

It depends on the problem.

  • Prefer iteration when a simple loop solves the problem (factorial, Fibonacci, sum of numbers): it is faster, uses constant extra memory and avoids stack overflow. For Fibonacci the recursive version repeats work and makes an exponential number of calls (O(2ⁿ)), while the loop takes n steps.
  • Prefer recursion when the problem is naturally recursive and the iterative form is complex: Tower of Hanoi, tree traversals, divide-and-conquer sorting (quick sort, merge sort), backtracking.

So for ordinary repetitive tasks I prefer the iterative algorithm; for hierarchical or divide-and-conquer problems recursion gives shorter and clearer code.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 5 questions →