Recursion (computer science): Difference between revisions

Revision as of 00:11, 23 November 2022

Revision as of 21:03, 23 November 2022

Line 268:

==Recursion versus iteration==

Recursion and [[iteration]] are equally expressive: recursion can be replaced by iteration with an explicit [[call stack]], while iteration can be replaced with [[tail call|tail recursion]],. whichWhich approach is preferable depends on the problem under consideration and the language used. In [[imperative programming]], iteration is preferred, particularly for simple recursion, as it avoids the overhead of function calls and call stack management, but recursion is generally used for multiple recursion. By contrast, in [[functional programming|functional languages]] recursion is preferred, with tail recursion optimization leading to little overhead. Implementing an algorithm using iteration may not be easily achievable.

Compare the templates to compute x_n defined by x_n = f(n, x_n-1) from x_base: