récurrence

In mathematics, récurrence, often translated as recurrence or recursion, refers to a method where a problem is solved by breaking it down into smaller, similar subproblems. This typically involves defining a function or sequence in terms of itself. A common example is the Fibonacci sequence, where each number is the sum of the two preceding ones. The definition typically includes a base case, which provides a direct solution for the simplest form of the problem, and a recursive step, which describes how to solve a larger problem using the solution of a smaller one. This process continues until the base case is reached.

Recurrence relations are fundamental in various areas of mathematics, including combinatorics, computer science, and discrete mathematics. They are used to model phenomena that exhibit self-similarity or exhibit growth patterns that depend on previous states. For instance, in computer science, recursive algorithms are widely employed. While elegant, recursive solutions can sometimes be inefficient due to repeated calculations of the same subproblems. Techniques like memoization or dynamic programming are often used to optimize these recursive processes by storing the results of subproblems to avoid recomputing them. The concept of recurrence is a powerful tool for understanding and solving complex problems by leveraging their inherent structure.