Recursion

A recursive rule refers to itself when defining or performing a calculation. Summing a list, for example, can combine its first value with the sum of the rest. A complete definition specifies both the decomposition and a base case, such as an empty list, from which results can be assembled.

References: [1]

A base case alone does not ensure termination. Each recursive step must make suitable progress, such as shortening a list or reducing a nonnegative counter. Invalid assumptions or cycling states can prevent completion. Termination is a property to justify about the algorithm, not a benefit automatically supplied by recursive syntax.

References: [2]

Recursive definitions can generate different processes. One factorial procedure leaves multiplications pending until inner calls return; another carries an accumulated product forward. Tail-call support changes the required control space. Merely observing that a function calls itself therefore does not establish its stack requirements or total memory consumption.

References: [1]

Trees and nested structures naturally support recursive traversal through their children. Recomputing overlapping subproblems can nevertheless multiply the work. Caching results or changing the decomposition changes those costs. Recursion expresses structure; efficiency still depends on the number of subproblems, repeated calculations, and the data retained during execution.

References: [2]