In how many distinct orders can n people line up? (This is n!.) Compute it with
recursion — think of it as choosing who stands first, then arranging the rest.
liningUp(n)
Assume 0 <= n. There is exactly one way to line up zero people (the empty line).
liningUp(3) // → 6
liningUp(1) // → 1
liningUp(0) // → 1
The simplest member of the exhaustive-recursion family — worth understanding as a foundation, since "decision, then recurse on what's left" reappears everywhere else in this section.
Focus on one decision: who stands first? n possible choices. Whichever you pick, the remaining n-1 people still need arranging in the remaining spots — and the count of ways to arrange them doesn't depend on who went first, since the problem is identical in structure with one fewer person.
Total arrangements: (choices for first spot) times (ways to arrange everyone else) = n * liningUp(n - 1) — multiply because for every choice of first person, all liningUp(n-1) arrangements of the rest are possible.
Zero people left has exactly one arrangement: the empty one. This is essential — without a base case of 1 (not 0), every liningUp(n) would collapse to 0.
Every line-up has some specific person first. Grouping all n! orderings by who's first splits them into n equal groups of (n-1)! each — exactly what the recursive formula computes. No ordering is double-counted (each belongs to exactly one group) or missed (every person is a valid first-slot candidate).
"Peel off one choice, multiply by arrangements of what's left" is the essence of how factorials arise in combinatorics — the same decision-tree thinking as generating actual permutations, just counting leaves instead of collecting arrangements.
def lining_up(n):
if n == 0:
return 1
return n * lining_up(n - 1)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.