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.

— Niklaus Wirth, Algorithms + Data Structures = Programs, 1976

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 looping constructs but rely solely on recursion to repeatedly call code. It is proved in computability theory that these recursive-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.^{[citation needed]}

The development of recursion in computer science grew out of mathematical logic and later became an essential part of programming language design. The early work done by Church, Gödel, Kleene, and Turing on recursive function and computability laid the groundwork that made recursion possible in programming languages. Recursion has been used by mathematicians for a long time, but it only became a practical tool for programming in the late 1950s and early 1960s. Key figures such as John McCarthy and the ALGOL 60 design committee contributed to introducing recursion into programming.

John McCarthy took the first steps by creating the programming language LISP in 1960. In his paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, McCarthy showed that recursion could be core in a programming language that works with symbols by processing them step by step. In LISP, recursion could be used in functions using simple rules, and there was also a way to evaluate them in the language. This demonstrated that recursion was a practical way to write programs and that it also describes the process of computation. Therefore, LISP became one of the first programming languages to use recursion as a main feature, and later on also influenced other languages that followed.

During that time, recursion was also added to ALGOL 60. The Report on the Algorithmic Language ALGOL 60, which was published in 1960, was the outcome of an international attempt at designing a standard language. Allowing procedures to call themselves was one of the new important features of the language. Before that, only loops were allowed to be used by programmers, so it was a significant change. Recursion allowed programmers to describe algorithms in a more natural and flexible way. Therefore, recursion was seen as something theoretically important and practically useful by computer scientists.