Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Recursion
Summary
Recursion occurs when the definition of a concept or process depends on a simpler version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references can occur.
A process that exhibits recursion is recursive.
In mathematics and computer science, a class of objects or methods exhibits recursive behavior when it can be defined by two properties:
A simple base case (or cases) — a terminating scenario that does not use recursion to produce an answer
A recursive step — a set of rules that reduces all successive cases toward the base case.
For example, the following is a recursive definition of a person's ancestor. One's ancestor is either:
One's parent (base case), or
One's parent's ancestor (recursive step).
The Fibonacci sequence is another classic example of recursion:
Fib(0) = 0 as base case 1,
Fib(1) = 1 as base case 2,
For all integers n > 1, Fib(n) = Fib(n − 1) + Fib(n − 2).
Many mathematical axioms are based upon recursive rules. For example, the formal definition of the natural numbers by the Peano axioms can be described as: "Zero is a natural number, and each natural number has a successor, which is also a natural number." By this base case and recursive rule, one can generate the set of all natural numbers.
Other recursively defined mathematical objects include factorials, functions (e.g., recurrence relations), sets (e.g., Cantor ternary set), and fractals.
There are various more tongue-in-cheek definitions of recursion; see recursive humor.
Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself. A procedure that goes through recursion is said to be 'recursive'.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (1)
Related people (3)
Related concepts (60)
Recursion (computer science)
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.
Function (mathematics)
In mathematics, a function from a set X to a set Y assigns to each element of X exactly one element of Y. The set X is called the domain of the function and the set Y is called the codomain of the function. Functions were originally the idealization of how a varying quantity depends on another quantity. For example, the position of a planet is a function of time. Historically, the concept was elaborated with the infinitesimal calculus at the end of the 17th century, and, until the 19th century, the functions that were considered were differentiable (that is, they had a high degree of regularity).
Recursion
Recursion occurs when the definition of a concept or process depends on a simpler version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references can occur.
Related courses (19)
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
MATH-381: Mathematical logic
Branche des mathématiques en lien avec le fondement des mathématiques et l'informatique théorique. Le cours est centré sur la logique du 1er ordre et l'articulation entre syntaxe et sémantique.
CS-119(g): Information, Computation, Communication
L'objectif de ce cours est d'initier les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de
l'informatique et des communications et de développer une première compétence
Related lectures (171)
Understanding Chaos in Quantum Field Theories
Explores chaos in quantum field theories, focusing on conformal symmetry, OPE coefficients, and random matrix universality.
Logic and Algorithms
Covers logic, mathematical reasoning, basic structures, and algorithms, exploring proofs, sets, functions, and recursion.
Recursion: introduction
Introduces recursion in algorithms, focusing on termination conditions and EPFL principles.