Method

Recursion (computer science)

Overview

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages (for instance, Clojure) do not define any built-in looping constructs, and instead rely solely on recursion. It is proved in computability theory that these recursion-only languages are Turing complete; this means that they are as powerful (they can be used to solve the same problems) as imperative languages based on control structures such as while and for.

Repeatedly calling a function from within itself may cause the call stack to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less efficient, and, for certain problems, algorithmic or compiler-optimization techniques such as tail call optimization may improve computational performance over a naive recursive implementation.

Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).

Possible passages

Found by search and not yet checked by a person; they may only mention the idea in passing.

Any number, considered as formed from any other number, is called a function of it; and there are as many kinds of functions as there are modes of formation. The simple functions are by no means numerous, most functions being formed by the combination of several of the operations which form simple functions, or by successive repetitions of some one of those operations. The simple functions of any number _x_ are all…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what Recursion is.
Read the chapter · Open in the reader
This is nothing else than the necessity of abstract logic, which is the presupposition involved in the very fact of interrelated existence as disclosed in each immediate occasion of experience. The key to the pattern means this fact:—that from a select set of those general conditions, exemplified in any one and the same occasion, a pattern involving an infinite variety of other such conditions, also exemplified in…
Alfred North Whitehead, Science and the modern world
States what Recursion is.
Read the chapter · Open in the reader
To trace in concrete detail the attainment of modern refinements of number theory would likewise exhibit nothing new in the building up of mathematical intelligence. We should find, here, a process carried out without thought of the consequences, there, an analogy suggesting an operation that might lead us beyond a difficulty that had blocked progress; here, a play interest leading to a combination of symbols out of…
John Dewey, Creative Intelligence
Close in meaning to Recursion; the term itself is not named.
Read the chapter · Open in the reader

Related ideas

Place in the tradition

Part of Outline of logic.

Explore Recursion (computer science) in the interactive graph →