Recursion (computer science): Difference between revisions

Revision as of 08:07, 16 August 2024

Revision as of 21:16, 13 September 2024

Line 1:

{{Short description|Use of functions that call themselves}}

{{About|recursive approaches to solving problems

|proofs by recursion|Mathematical induction

|recursion in computer science acronyms|Recursive acronym#Computer-related examples{{!}}Recursive acronym § Computer-related examples

|general use of the term|Recursion}}

{{Use dmy dates|date=March 2020|cs1-dates=y}}

{{Use dmy dates|date=March 2020|cs1-dates=y}}

[[File:recursiveTree.JPG|thumb|300px|Tree created using the [[Logo (programming language)|Logo programming language]] and relying heavily on recursion. Each branch can be seen as a smaller version of a tree.]]

[[File:Sierpinski triangle turtle.gif|thumb|Recursive drawing of a [[Sierpiński triangle|Sierpiński Triangle]] through turtle graphics.]]

Line 42 ⟶ 41:

}}</ref>}}

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 certain problems, algorithmic or compiler-optimization techniques such as [[tail call]] optimization may improve computational performance over a naive recursive implementation.

Line 49 ⟶ 48:

==Recursive functions and algorithms==

A common [[Algorithm#Design|algorithm design]] tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the [[divide-and-conquer method]]; when combined with a [[lookup table]] that stores the results of previously solved sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as [[dynamic programming]] or [[memoization]]{{sic|hide=y}}.

===Base case===

Line 60 ⟶ 59:

==Recursive data types==

Many [[computer program]]s must process or generate an arbitrarily large quantity of [[data]]. Recursion is a technique for representing data whose exact size is unknown to the [[programmer]]: the programmer can specify this data with a [[Self reference|self-referential]] definition. There are two types of self-referential definitions: inductive and [[Coinduction|coinductive]] definitions.

{{further|Algebraic data type}}

Line 67 ⟶ 66:

{{main|Recursive data type}}

An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, [[linked list]]s can be defined inductively (here, using [[Haskell (programming language)|Haskell]] syntax):

<syntaxhighlight lang="haskell">data ListOfStrings = EmptyList | Cons String ListOfStrings</syntaxhighlight>

Line 275 ⟶ 274:

==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]]. Which 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:

Line 317 ⟶ 316:

In languages (such as [[C (programming language)|C]] and [[Java (programming language)|Java]]) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in [[functional languages]], a function call (particularly a [[tail call]]) is typically a very fast operation, and the difference is usually less noticeable.

As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the [[compiler]] used. In languages where looping constructs are preferred, the iterative version may be as much as several [[order of magnitude|orders of magnitude]] faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration.

===Stack space===

Line 329 ⟶ 328:

===Refactoring recursion===

Recursive algorithms can be replaced with non-recursive counterparts.<ref>{{cite web| last=Mitrovic| first=Ivan| title=Replace Recursion with Iteration| publisher=[[ThoughtWorks]]| url=https://www.refactoring.com/catalog/replaceRecursionWithIteration.html}}</ref> One method for replacing recursive algorithms is to simulate them using [[memory management|heap memory]] in place of [[stack-based memory allocation|stack memory]].<ref>{{cite web| last=La| first=Woong Gyu| title=How to replace recursive functions using stack and while-loop to avoid the stack-overflow| publisher=CodeProject| date=2015| url=https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and}}</ref> An alternative is to develop a replacement algorithm entirely based on non-recursive methods, which can be challenging.<ref>{{cite web| last=Moertel| first=Tom| title=Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick| date=2013| url=http://blog.moertel.com/posts/2013-05-14-recursive-to-iterative-2.html}}</ref> For example, recursive algorithms for [[matching wildcards]], such as [[Rich Salz]]' [[wildmat]] algorithm,<ref>{{cite web| last=Salz| first=Rich| title=wildmat.c| publisher=[[GitHub]]| date=1991| url=https://github.com/trevor/transmission/blob/master/libtransmission/wildmat.c}}</ref> were once typical. Non-recursive algorithms for the same purpose, such as the [[Krauss matching wildcards algorithm]], have been developed to avoid the drawbacks of recursion<ref>{{cite magazine| last=Krauss| first=Kirk J.| title=Matching Wildcards: An Algorithm| magazine=[[Dr. Dobb's Journal]]| date=2008| url=http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-algorithm/210200888}}</ref> and have improved only gradually based on techniques such as collecting [[software testing|tests]] and [[profiling (computer programming)|profiling]] performance.<ref>{{cite web| last=Krauss| first=Kirk J.| title=Matching Wildcards: An Improved Algorithm for Big Data| publisher=Develop for Performance| date=2018| url=http://www.developforperformance.com/MatchingWildcards_AnImprovedAlgorithmForBigData.html}}</ref>

==Tail-recursive functions==