Recursion

Permutations

Permutations builds every possible ordering of k values by keeping a shared prefix of the values chosen so far. At each call, it tries every value not already in the prefix: it adds that value, recurses to extend the prefix further, and once that recursion has explored everything it can, removes the value again before trying the next one.

When it is the right choice

Generating every permutation is only practical for small k, since there are k! of them — 5! is 120, 10! is over three million. The technique it demonstrates, backtracking, generalises far beyond permutations: constraint satisfaction, the eight queens problem and combinatorial search all follow the same shape of choose, recurse, undo. This page is the first and simplest place to see that shape clearly.

How it works

• Call permute with the shared prefix and the set of values already used.
• If the prefix already contains every value, it is a complete arrangement: record it and hand back.
• Otherwise, for each value not yet in the prefix, mark it used and append it to the prefix.
• Call permute again with the extended prefix, and wait for every arrangement that choice could lead to.
• Remove that value from the prefix and mark it unused again, restoring the state to what it was before the choice was tried, then move on to the next value.

Worth noticing

• The restore step is the lesson: without it, the next value tried at this position would see the previous one still marked used, and whole branches of the search would silently vanish.
• The working prefix shown beside the stack is exactly the state being mutated and restored — watch it grow on the way into a branch and shrink back on the way out, in lockstep with the calls counter.
• The call count is not k! itself but a bit more: every partial prefix is a call too, not only the k!-many complete ones, so the total is the sum of arrangements of every length from 0 to k.

Cost

Best

O(k!)

Average

O(k!)

Worst

O(k!)

Extra space

O(k)

Largest input

n = 5

The largest input is a pedagogical ceiling rather than a technical one. This algorithm makes k! calls, and past n = 5 the run stops being something a person can sit and watch — long before it reaches the step limit the tool enforces.

Worth comparing

• Towers of Hanoi — The other algorithm here that does work on the way back up, though Hanoi's "up" step is a single move rather than an undo.
• Fibonacci, naive — A tree that branches for a different reason: Fibonacci branches to combine two answers, permutations branches to try every remaining choice.

All recursive algorithms