= Recursion
{disambiguate=computer science}
{wiki}
= Recursion
{synonym}
<Recursion> solves a problem by invoking the same procedure on smaller instances, with base cases answered directly. For <merge sort>, an empty or one-entry <array> is already sorted, and every larger <array> is split into two shorter parts. The decreasing lengths justify termination; a self-call without a progress rule would not suffice.
A <recursive procedure> refers to itself, directly or through another procedure. A <recursive call> starts another invocation, with its own arguments and local <variables>; the caller can wait for its returned <output>. A <base case> supplies an answer without further <recursive calls>. To establish <algorithm termination>, also show that every <recursive call> progresses in a <well-founded relation>. “Smaller” means smaller in that chosen relation: argument values need not all decrease, and the arguments need not even be numbers.
<Recursion> is especially expressive when a <data structure> already decomposes into smaller structures. A <binary tree> has two child <subtrees>, so <structural recursion> can follow its shape. A short rule for each case can describe an entire traversal or computation. The distinction between a <recursive procedure> and the <recursive process> it generates helps connect that compact description to its resource use.<Structure and Interpretation of Computer Programs by Harold Abelson and others>[Structure and Interpretation of Computer Programs, second edition, §1.2.1: procedure versus process; §1.2.2: closing discussion before Counting change, hierarchical data and straightforward definitions]{ref}
Back to article page
