BacktrackingRecursion & Backtracking

Recursion (factorial)

Solve a problem by reducing it to smaller copies of itself; backtracking explores a tree of partial choices and undoes each one after exploring it.

n — Integer between 1 and 8

Call stack (top first)

fact(5)

n=5

Recursion tree

1/15Call fact(5): a new frame is pushed on top of the stack. Nothing is computed yet because the answer depends on fact(4).

Call on the stackCall returned

1fact(n):
2  if n <= 1: return 1        // base case
3  sub = fact(n - 1)          // recursive case
4  return n * sub

Variables

depth1

Complexity

worst O(b^d · cost per node)

space O(d)

Speed