recurses

Recurses is the third-person singular present tense of the verb recurse, and by extension refers to the act of applying a recursive method. In mathematics, computer science, and related fields, recursion is a problem-solving technique in which a process solves a problem by invoking itself to handle subproblems that resemble the original problem.

Typically a recursive solution includes a base case that stops further recursion and a recursive step that reduces the problem size. Properly defined, repeated application of the recursive step approaches the base case, ensuring termination. Without a base case or with steps that do not reduce the problem, the process can continue indefinitely, producing infinite recursion and eventually a stack overflow in practical systems.

Recursion can be direct, when a function calls itself, or mutual, when two or more functions call each other in a cycle. Some languages optimize tail-recursive procedures, where the recursive call is the last operation, allowing space usage comparable to iteration.

Classical examples include factorials and traversing tree-like structures. For instance, factorial(n) can be defined as n * factorial(n-1) with factorial(0) = 1. Recursion also provides natural descriptions for operations on hierarchical data, such as file systems or parse trees. In practice, recursive solutions trade simplicity and expressiveness for potential overhead and stack depth limitations, and may be combined with techniques such as memoization to improve efficiency.

Related concepts include recursion, tail recursion, mutual recursion, and stack overflow.