Recursion (computer science): Difference between revisions

Revision as of 16:58, 11 June 2022

Latest revision as of 18:24, 20 July 2025

(45 intermediate revisions by 27 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.]]

{{Programming paradigms}}

[[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 13 ⟶ 17:

| chapter-url = http://www-cs-faculty.stanford.edu/~knuth/gkp.html

| chapter=1: Recurrent Problems

|publisher = Addison-Wesley

}}</ref><ref>{{cite journal|title=Teaching Recursive Thinking using Unplugged Activities|journal=WTE&TEWorld Transactions on Engineering and Technology Education|volume=19|pages=169 - 175169–175|year=2021|last1=Kuhail|first1=M. A. |last2=Negreiros|first2=J. |last3=Seffah|first3=A. |url = http://www.wiete.com.au/journals/WTE&TE/Pages/Vol.19,%20No.%202%20(2021)/03-Kuhail-M.pdf}}</ref> Recursion solves such [[recursion|recursive problems]] by using [[function (computer science)|functions]] that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.<ref>{{cite book

|author-last = Epp

|author-first = Susanna

Line 21 ⟶ 26:

|edition = 2nd

|page = [https://archive.org/details/discretemathema000epps/page/427 427]

|publisher = PWS Publishing Company

|url = https://archive.org/details/discretemathema000epps/page/427

}}</ref>

Line 35 ⟶ 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 largecertain problems, italgorithmic is fundamental to useor compiler-optimization techniques such as [[tail call]] optimization.{{CN|date=November 2019}}may improve computational performance over a naive recursive implementation.

{{toclimit|3}}

==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 53 ⟶ 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 60 ⟶ 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 179 ⟶ 185:

}

</syntaxhighlight>

| VALIGN=TOP | <syntaxhighlight lang=C"c">

static int fac2(int n) {

// assert(n >= 2);

if (n == 2)

Line 262 ⟶ 268:

</syntaxhighlight>

Note the use of [[short-circuit evaluation]] of the Boolean &amp;&amp; (AND) operators, so that the recursive call is made only if the node is valid (non-Null). Note that while the first term in the AND is a pointer to a node, the second term is a booleanBoolean, so the overall expression evaluates to a booleanBoolean. This is a common idiom in recursive short-circuiting. This is in addition to the short-circuit evaluation of the Boolean || (OR) operator, to only check the right child if the left child fails. In fact, the entire [[control flow]] of these functions can be replaced with a single Boolean expression in a return statement, but legibility suffers at no benefit to efficiency.

===Hybrid algorithm===

Line 268 ⟶ 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 274 ⟶ 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 310 ⟶ 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 322 ⟶ 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 355 ⟶ 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 381 ⟶ 388:

[[Image:Recursive2.svg|350px]]

FunctionThe output of function 2 is that of function 1 with the lines swapped.

In the case of a function calling itself only once, instructions placed before the recursive call are executed once per recursion before any of the instructions placed after the recursive call. The latter are executed repeatedly after the maximum recursion has been reached.

Line 824 ⟶ 831:

where {{mvar|a}} represents the number of recursive calls at each level of recursion, {{mvar|b}} represents by what factor smaller the input is for the next level of recursion (i.e. the number of pieces you divide the problem into), and {{math|''f''(''n'')}} represents the work that the function does independently of any recursion (e.g. partitioning, recombining) at each level of recursion.

==Recursion in Logic Programming==

In the procedural interpretation of [[logic programming|logic programs]], clauses (or rules) of the form <syntaxhighlight inline lang="prolog">A :- B</syntaxhighlight> are treated as procedures, which reduce goals of the form <code>A</code> to subgoals of the form <code>B</code>.

For example, the [[Prolog]] clauses:

<syntaxhighlight lang="prolog">

path(X,Y) :- arc(X,Y).

path(X,Y) :- arc(X,Z), path(Z,Y).

</syntaxhighlight>

define a procedure, which can be used to search for a path from ''X'' to ''Y'', either by finding a direct arc from ''X'' to ''Y'', or by finding an arc from ''X'' to ''Z'', and then searching recursively for a path from ''Z'' to ''Y''. Prolog executes the procedure by reasoning top-down (or [[backward chaining|backwards]]) and searching the space of possible paths depth-first, one branch at a time. If it tries the second clause, and finitely fails to find a path from ''Z'' to ''Y'', it backtracks and tries to find an arc from ''X'' to another node, and then searches for a path from that other node to ''Y''.

However, in the logical reading of logic programs, clauses are understood [[declarative program|declaratively]] as universally quantified conditionals. For example, the recursive clause of the path-finding procedure is understood as [[Knowledge representation and reasoning|representing the knowledge]] that, for every ''X'', ''Y'' and ''Z'', if there is an arc from ''X'' to ''Z'' and a path from ''Z'' to ''Y'' then there is a path from ''X'' to ''Y''. In symbolic form:

:<math>\forall X, Y, Z(arc(X,Z)\land path(Z,Y) \rightarrow path(X,Y)).</math>

The logical reading frees the reader from needing to know how the clause is used to solve problems. The clause can be used top-down, as in Prolog, to reduce problems to subproblems. Or it can be used bottom-up (or [[forward chaining|forwards]]), as in [[Datalog]], to derive conclusions from conditions. This [[separation of concerns]] is a form of [[Abstraction (computer science)|abstraction]], which separates declarative knowledge from problem solving methods (see [[Algorithm#Algorithm = Logic + Control]]).<ref>{{Cite book

| 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

| isbn = 978-0134610993

| lccn = 20190474

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

Line 831 ⟶ 881:

* [[Kleene–Rosser paradox]]

* [[Open recursion]]

* [[Recursion]] (in general)

* [[Sierpiński curve]]

* [[McCarthy 91 function]]

Line 837 ⟶ 887:

* [[Primitive recursive function]]s

* [[Tak (function)]]

* [[Logic programming]]

==Notes==

Line 854 ⟶ 905:

{{refend}}

{{Programming paradigms navbox}}

{{Data structures and algorithms}}

{{Algorithmic paradigms}}

{{DEFAULTSORT:Recursion (Computer Science)}}

[[Category:Theoretical computer science]]