**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.
Formal definitions
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.

Official source

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

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people (3)

Related units (2)

Related publications (16)

Loading

Loading

Loading

Related courses (24)

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 as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.

CS-550: Formal verification

We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to use formal verification tools and explain the theory and the practice behind them.

CS-420: Advanced compiler construction

Students learn several implementation techniques for modern functional and object-oriented programming languages. They put some of them into practice by developing key parts of a compiler and run time system for a simple functional programming language.

Related concepts (55)

Fractal

In mathematics, a fractal is a geometric shape containing detailed structure at arbitrarily small scales, usually having a fractal dimension strictly exceeding the topological dimension. Many fr

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 dom

Mathematics

Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These top

Stéphane Magnenat, Francesco Mondada, Martin Voelkle

Autonomous mobile robots are promising tools for operations in environments that are difficult to access for humans. When these environments are dynamic and non-deterministic, like in collapsed buildings, the robots must coordinate their actions and the use of resources using planning. This paper presents Planner9, a hierarchical task network (HTN) planner that runs on groups of miniature mobile robots. These robots have limited computational power and memory, but are well connected through Wi-Fi. Planner9 takes advantage of this connectivity to distribute the planning over different robots. We have adapted the HTN algorithm to perform parallel search using A* and to limit the number of search nodes through lifting. We show that Planner9 scales well with the number of robots, even on non-linear tasks that involve recursions in their decompositions. We show that contrary to JSHOP2, Planner9 finds optimal plans.

Related lectures (69)

Francesca Bonizzoni, Fabio Nobile

We study the Darcy boundary value problem with lognormal permeability field. We adopt a perturbation approach, expanding the solution in Taylor series around the nominal value of the coefficient, and approximating the expected value of the stochastic solution of the PDE by the expected value of its Taylor polynomial. The recursive deterministic equation satisfied by the expected value of the Taylor polynomial (first moment equation) is formally derived. Well-posedness and regularity results for the recursion are proved to hold in Sobolev space-valued Hölder spaces with mixed regularity. The recursive first moment equation is then discretized by means of a sparse approximation technique, and the convergence rates are derived.

2020Francesca Bonizzoni, Fabio Nobile

We study the Darcy boundary value problem with log-normal permeability field. We adopt a perturbation approach, expanding the solution in Taylor series around the nominal value of the coefficient, and approximating the expected value of the stochastic solution of the PDE by the expected value of its Taylor polynomial. The recursive deterministic equation satisfied by the expected value of the Taylor polynomial (first moment equation) is formally derived. Well-posedness and regularity results for the recursion are proved to hold in Sobolev space-valued Hölder spaces with mixed regularity. The recursive first moment equation is then discretized by means of a sparse approximation technique, and the convergence rates are derived.