Recursion (computer science): Difference between revisions

Revision as of 05:51, 16 August 2024

Latest revision as of 18:24, 20 July 2025

(9 intermediate revisions by 9 users not shown)

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}}

[[File:recursiveTree.JPG|thumb|300px|Tree fractal 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.]]

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

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

[[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.]]

In [[computer science]], '''recursion''' is a method of solving a [[computational problem]] where the solution depends on solutions to smaller instances of the same problem.<ref>{{cite book

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 281 ⟶ 280:

|-

|

'''function''' recursive(n)

'''if''' n == base

'''return''' x_base

'''else'''

'''return''' f(n, recursive(n - 1))

||

'''function''' iterative(n)

x = x_base

'''for''' i = base + 1 to n

x = f(i, x)

'''return''' x

|}

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==

Line 362 ⟶ 361:

The significance of tail recursion is that when making a tail-recursive call (or any tail call), the caller's return position need not be saved on the [[call stack]]; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, in languages that recognize this property of tail calls, tail recursion saves both space and time.

==Order of execution==

Line 851:

| first1 = Stuart J. | last1 = Russell | author1-link = Stuart J. Russell

| first2 = Peter. | last2 = Norvig | author2-link = Peter Norvig

| title=[[Artificial Intelligence: A Modern Approach]]|Artificial Intelligence: A Modern Approach §9.3, §9.4]]

| year = 2021

| edition = 4th

Line 858:

| publisher = Pearson | ___location = Hoboken

}}</ref>

== Infinite recursion ==

{{See also|Infinite loop#Infinite recursion}}

A common mistake among programmers is not providing a way to exit a recursive function, often by omitting or incorrectly checking the base case, letting it run (at least theoretically) infinitely by endlessly calling itself recursively. This is called ''infinite recursion'', and the program will never terminate. In practice, this typically exhausts the available [[Stack (abstract data type)|stack]] space. In most programming environments, a program with infinite recursion will not really run forever. Eventually, something will break and the program will report an error.<ref>{{Cite web |title=4.8. Infinite Recursion |url=https://runestone.academy/ns/books/published/thinkcpp/Chapter4/InfiniteRecursion.html}}</ref>

Below is a Java code that would use infinite recursion:<syntaxhighlight lang="java" line="1">public class InfiniteRecursion {

static void recursive() { // Recursive Function with no way out

recursive();

}

public static void main(String[] args) {

recursive(); // Executes the recursive function upon runtime

}

}</syntaxhighlight>

Running this code will result in a [[stack overflow]] error.

==See also==

* [[Recursion (computer science)]]

* [[Functional programming]]

* [[Computational problem]]