Editing Recursion (section)

==In computer science==
{{Main|Recursion (computer science)}}
A common method of simplification is to divide a problem into subproblems of the same type. As a [[computer programming]] technique, this is called [[divide and conquer algorithm|divide and conquer]] and is key to the design of many important algorithms. Divide and conquer serves as a top-down approach to problem solving, where problems are solved by solving smaller and smaller instances. A contrary approach is [[dynamic programming]]. This approach serves as a bottom-up approach, where problems are solved by solving larger and larger instances, until the desired size is reached.

A classic example of recursion is the definition of the [[factorial]] function, given here in [[Python (programming language)|Python]] code:

<syntaxhighlight lang="python3">def factorial(n):
    if n > 0:
        return n * factorial(n - 1)
    else:
        return 1  
</syntaxhighlight>

The function calls itself recursively on a smaller version of the input {{code|(n - 1)}} and multiplies the result of the recursive call by {{code|n}}, until reaching the [[base case (recursion)|base case]], analogously to the mathematical definition of factorial.

Recursion in computer programming is exemplified when a function is defined in terms of simpler, often smaller versions of itself. The solution to the problem is then devised by combining the solutions obtained from the simpler versions of the problem. One example application of recursion is in [[parser]]s for programming languages. The great advantage of recursion is that an infinite set of possible sentences, designs or other data can be defined, parsed or produced by a finite computer program.

[[Recurrence relation]]s are equations which define one or more sequences recursively. Some specific kinds of recurrence relation can be "solved" to obtain a non-recursive definition (e.g., a [[closed-form expression]]).

Use of recursion in an algorithm has both advantages and disadvantages.  The main advantage is usually the simplicity of instructions. The main disadvantage is that the memory usage of recursive algorithms may grow very quickly, rendering them impractical for larger instances.