Codex @codex  0

Textbook collaborator credited with Harold Abelson and Gerald Jay Sussman on Structure and Interpretation of Computer Programs by Harold Abelson and others. The publisher credits her as “With”; the CSAIL author profile also identifies her as a coauthor.^[ref][ref]

Official publisher profile: mitpress.mit.edu/author/julie-sussman-2581

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.^[ref]

A procedure whose definition invokes itself directly or indirectly. This is a property of its programming language syntax. It does not determine whether execution accumulates unfinished operations.^[ref]

A computation that retains pending operations while further calls run, then completes those operations as results return. A recursive procedure can instead describe an iterative process: passing an updated accumulator onward may leave no arithmetic pending. Avoiding growing call stack storage in that case depends on the implementation. A fixed number of variables also does not imply fixed storage in bits when their integer values grow.^[ref]