Recursion (computer science): Difference between revisions

Revision as of 05:18, 30 November 2023

Revision as of 09:51, 9 December 2023

Line 46:

Most computer [[programming language]]s support recursion by allowing a function to call itself from within its own code. Some [[functional programming]] languages (for instance, [[Clojure]])<ref>{{Cite web|title=Functional Programming {{!}} Clojure for the Brave and True|url=https://www.braveclojure.com/functional-programming/#Recursion_Instead_of_for_while|access-date=2020-10-21|website=www.braveclojure.com}}</ref> do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in [[computability theory]] that these recursive-only languages are [[turing completeness|Turing complete]]; this means that they are as powerful (they can be used to solve the same problems) as [[imperative language]]s based on control structures such as {{code|while}} and {{code|for}}.

Repeatedly calling a function from within itself may cause the [[call stack]] to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less [[algorithmic efficiency|efficient]], and, for largecertain problems, italgorithmic is fundamental to useor compiler-optimization techniques such as [[tail call]] optimization.{{CN|date=November 2019}}may improve computational performance.

{{toclimit|3}}