text:
Biathlon at the 2002 Winter Olympics
From Wikipedia, the free encyclopedia
Jump to: navigation, search
Biathlon
at the XIX Olympic Winter Games
Andrea Nahrgang competing at Soldier Hollow at the 2002 Winter Olympics.
Venue
Soldier Hollow
Dates
9-20 February
No. of events
8
Competitors
190 from 34 nations
← 1998
2006 →
Biathlon at the
2002 Winter Olympics
Individual
men women
Sprint
men women
Pursuit
men women
Relay
men women
v
t
e
Frode Andresen competing at Soldier Hollow at the 2002 Winter Olympics.
Jeremy Teela competing at Soldier Hollow at the 2002 Winter Olympics.
Biathlon at the 2002 Winter Olympics consisted of eight biathlon events. They were held at Soldier Hollow. The events began on 11 February and ended on 20 February 2002.[1] For the first time since 1992, the biathlon program expanded. A new race type, the pursuit was added, the first new race type since the debut of the sprint in 1980.
Contents
[hide]
1 Medal summary
1.1 Medal table
1.2 Men's events
1.3 Women's events
2 Participating nations
3 See also
4 References
Medal summary[edit]
Seven nations won medals in biathlon, with Germany winning the most (3 gold, 5 silver, 1 bronze), while Norway led the medal table with 4 gold medals. These four all involved Ole Einar Bjørndalen, who won each of the three men's individual events, as well as participating in the gold-medal winning relay team. Kati Wilhelm was the most successful athlete in the women's competition, taking two golds and a silver.
Medal table[edit]
Rank
Nation
Gold
Silver
Bronze
Total
1 Norway (NOR) 4 2 0 6
2 Germany (GER) 3 5 1 9
3 Russia (RUS) 1 0 2 3
4 France (FRA) 0 1 1 2
5 Sweden (SWE) 0 0 2 2
6 Austria (AUT) 0 0 1 1
Bulgaria (BUL) 0 0 1 1
Total
8
8
8
24
Men's events[edit]
Event
Gold
Silver
Bronze
Individual
details Ole Einar Bjørndalen
Norway 51:03.3 Frank Luck
Germany 51:39.4 Viktor Maigourov
Russia 51:40.6
Sprint
details Ole Einar Bjørndalen
Norway 24:51.3 Sven Fischer
Germany 25:20.2 Wolfgang Perner
Austria 25:44.4
Pursuit
details Ole Einar Bjørndalen
Norway 32:34.6 Raphaël Poirée
France 33:17.6 Ricco Groß
Germany 33:30.6
Relay
details Norway (NOR)
Halvard Hanevold
Frode Andresen
Egil Gjelland
Ole Einar Bjørndalen 1:23:42.3 Germany (GER)
Ricco Groß
Peter Sendel
Sven Fischer
Frank Luck 1:24:27.6 France (FRA)
Gilles Marguet
Vincent Defrasne
Julien Robert
Raphaël Poirée 1:24:36.6
Women's events[edit]
Event
Gold
Silver
Bronze
Individual
details Andrea Henkel
Germany 47:29.1 Liv Grete Skjelbreid-Poirée
Norway 47:37.0 Magdalena Forsberg
Sweden 48:08.3
Sprint
details Kati Wilhelm
Germany 20:41.4 Uschi Disl
Germany 20:57.0 Magdalena Forsberg
Sweden 21:20.4
Pursuit
details Olga Pyleva
Russia 31:07.8 Kati Wilhelm
Germany 31:13.1 Irina Nikulchina
Bulgaria 31:15.9
Relay
details Germany (GER)
Katrin Apel
Uschi Disl
Andrea Henkel
Kati Wilhelm 1:27:55.8 Norway (NOR)
Ann-Elen Skjelbreid
Linda Tjørhom
Gunn Margit Andreassen
Liv Grete Skjelbreid-Poirée 1:28:26.4 Russia (RUS)
Olga Pyleva
Galina Kukleva
Svetlana Ishmouratova
Albina Akhatova 1:29:20.5
Participating nations[edit]
Thirty-four nations sent biathletes to compete in the events. Below is a list of the competing nations; in parentheses are the number of national competitors. Chile and Croatia made their Olympic debuts in the sport, with one athlete each.
Argentina (2)
Austria (5)
Belarus (11)
Bulgaria (5)
Canada (1)
Chile (2)
China (5)
Croatia (1)
Czech Republic (10)
Estonia (4)
Finland (9)
France (10)
Great Britain (4)
Germany (11)
Greece (2)
Hungary (3)
Italy (10)
Japan (8)
Kazakhstan (2)
Kyrgyzstan (1)
South Korea (2)
Latvia (5)
Lithuania (2)
Moldova (2)
Norway (9)
Poland (5)
Romania (4)
Russia (11)
Slovenia (10)
Switzerland (4)
Slovakia (6)
Sweden (5)
Ukraine (11)
United States (8)
See also[edit]
Biathlon at the 2002 Winter Paralympics
References[edit]
Jump up ^ "Salt Lake City 2002 Official Report - Volume 1" (PDF). Salt Lake Organizing Committee. LA84 Foundation. 2002. Archived from the original (PDF) on May 6, 2010. Retrieved February 6, 2013.
Official Olympic Report
[show]
v
t
e
Biathlon at the Winter Olympics
Military patrol
1924
1928 (demonstration)
1932
1936 (demonstration)
1948 (demonstration)
1952
1956
Biathlon
1960
1964
1968
1972
1976
1980
1984
1988
1992
1994
1998
2002
2006
2010
2014
2018
List of medalists
List of venues
[show]
v
t
e
Events at the 2002 Winter Olympics (Salt Lake City)
Alpine skiing
Biathlon
Bobsleigh
Cross‑country skiing
Curling
Figure skating
Freestyle skiing
Ice hockey
Luge
Nordic combined
Short track speed skating
Skeleton
Ski jumping
Snowboarding
Speed skating
Retrieved from "https://en.wikipedia.org/w/index.php?title=Biathlon_at_the_2002_Winter_Olympics&oldid=833021314"
Categories:
2002 in biathlon
2002 Winter Olympics events
Biathlon at the Winter Olympics
Biathlon at the 2002 Winter Olympics
Biathlon competitions in the United States
Hidden categories:
Articles which use infobox templates with no data rows
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
In other projects
Wikimedia Commons
Languages
Bosanski
Català
Čeština
Deutsch
Eesti
Español
Français
한국어
Italiano
Magyar
Nederlands
日本語
Norsk
Norsk nynorsk
Plattdüütsch
Polski
Português
Русский
Slovenščina
Suomi
Svenska
Українська
中文
14 more
Edit links
This page was last edited on 29 March 2018, at 07:19.
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

values: mw-page-base noprint

values: mw-head-base noprint

values: firstHeading firstHeading en

values: siteSub noprint

values: jump-to-nav mw-jump

attrs: href class

attrs: scope style

values: row white-space:nowrap;

value: abbr

values: text-align:center;border-top: 1px solid #aaa; padding-top: 3px;

values: text-align:left;;line-height:1.4em;padding:0.1em 0.4em 0.2em 0.1em;font-weight:normal

values: Biathlon at the 2002 Winter Olympics – Men's individual

values: Biathlon at the 2002 Winter Olympics – Women's individual

values: Biathlon at the 2002 Winter Olympics – Men's sprint

values: Biathlon at the 2002 Winter Olympics – Women's sprint

values: Biathlon at the 2002 Winter Olympics – Men's pursuit

values: Biathlon at the 2002 Winter Olympics – Women's pursuit

values: Biathlon at the 2002 Winter Olympics – Men's relay

values: Biathlon at the 2002 Winter Olympics – Women's relay

values: Template:Biathlon at the 2002 Winter Olympics

values: Template talk:Biathlon at the 2002 Winter Olympics

values: float:right;clear:right;width:auto;max-width:25em;margin:0 0 1.0em 1.0em;background:#f5faff;border:1px solid #B8C7D9;padding:0.2em;border-spacing:0.4em 0;text-align:center;font-size:88%

values:
col
headerSort
0
columnheader button
Sort ascending

values:
col
background-color:gold; width:6em;
headerSort
0
columnheader button
Sort ascending

values:
col
background-color:silver; width:6em;
headerSort
0
columnheader button
Sort ascending

values:
col
background-color:#cc9966; width:6em;
headerSort
0
columnheader button
Sort ascending

values:
col
width:6em;
headerSort
0
columnheader button
Sort ascending

attrs: alt src title width height class srcset data-file-width data-file-height

values: wikitable sortable plainrowheaders jquery-tablesorter

values:
col
2
width: 200px; background: #FFD700;

values:
col
2
width: 200px; background: #CCCCCC;

values:
col
2
width: 200px; background: #CC9966;

values:
wikitable plainrowheaders
1
font-size: 100%

values:
/wiki/Liv_Grete_Skjelbreid-Poir%C3%A9e
mw-redirect
Liv Grete Skjelbreid-Poirée

values:
/wiki/Olga_Pyleva
mw-redirect
Olga Pyleva

values:
/wiki/Linda_Tj%C3%B8rhom
mw-redirect
Linda Tjørhom

values: Czech Republic at the 2002 Winter Olympics

values: Great Britain at the 2002 Winter Olympics

values: United States at the 2002 Winter Olympics

values: border-collapse: collapse; padding: 0; border: 0; background:transparent; width:100%;

values:
reflist mw-references-wrap
list-style-type: decimal;

values: Military patrol at the 1924 Winter Olympics

values: Military patrol at the 1928 Winter Olympics

values: Military patrol at the 1936 Winter Olympics

values: Military patrol at the 1948 Winter Olympics

values:
navbox-image
2
width:1px;padding:0px 0px 0px 2px

values: nowraplinks collapsible autocollapse navbox-inner

values: Template:Events at the 2002 Winter Olympics

values: Template talk:Events at the 2002 Winter Olympics

values:
/wiki/Salt_Lake_City,_Utah
mw-redirect
Salt Lake City, Utah

values: Alpine skiing at the 2002 Winter Olympics

values: Cross-country skiing at the 2002 Winter Olympics

values: Figure skating at the 2002 Winter Olympics

values: Freestyle skiing at the 2002 Winter Olympics

values: Nordic combined at the 2002 Winter Olympics

values: Short track speed skating at the 2002 Winter Olympics

values: Snowboarding at the 2002 Winter Olympics

values: Speed skating at the 2002 Winter Olympics

values: Category:Biathlon at the Winter Olympics

values: Category:Biathlon at the 2002 Winter Olympics

values: Category:Biathlon competitions in the United States

values: Category:Articles which use infobox templates with no data rows

values: Discussion about edits from this IP address [ctrl-alt-n]

values: A list of edits made from this IP address [ctrl-alt-y]

values: You are encouraged to create an account and log in; however, it is not mandatory

values: You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]

values: Discussion about the content page [ctrl-alt-t]

values: p-namespaces navigation vectorTabs p-namespaces-label

values:
p-variants
navigation
vectorMenu emptyPortlet
p-variants-label

values: Past revisions of this page [ctrl-alt-h]

values: p-views navigation vectorTabs p-views-label

values:
p-cactions
navigation
vectorMenu emptyPortlet
p-cactions-label

values:
mw-wiki-logo
/wiki/Main_Page
Visit the main page

values:
/wiki/Main_Page
Visit the main page [ctrl-alt-z]
z

values: Featured content – the best of Wikipedia

values: Find background information on current events

values:
/wiki/Special:Random
Load a random article [ctrl-alt-x]
x

values: About the project, what you can do, where to find things

values: A list of recent changes in the wiki [ctrl-alt-r]

values: portal navigation p-interaction p-interaction-label

values: List of all English Wikipedia pages containing links to this page [ctrl-alt-j]

values: Recent changes in pages linked from this page [ctrl-alt-k]

values:
/wiki/Wikipedia:File_Upload_Wizard
Upload files [ctrl-alt-u]
u

values: A list of all special pages [ctrl-alt-q]

values: Permanent link to this revision of the page

values: Link to connected data repository item [ctrl-alt-g]

values: Printable version of this page [ctrl-alt-p]

values: Biatlon na Zimskim olimpijskim igrama 2002. – Bosnian

values:
interlanguage-link interwiki-bs
display: none;

values: Biatló als Jocs Olímpics d'hivern de 2002 – Catalan

values:
interlanguage-link interwiki-ca
display: none;

values: Biatlon na Zimních olympijských hrách 2002 – Czech

values:
interlanguage-link interwiki-cs
display: none;

values: Olympische Winterspiele 2002/Biathlon – German

values: Laskesuusatamine 2002. aasta taliolümpiamängudel – Estonian

values:
interlanguage-link interwiki-et
display: none;

values: Anexo:Biatlón en los Juegos Olímpicos de Salt Lake City 2002 – Spanish

values: Biathlon aux Jeux olympiques de 2002 – French

values: 2002년 동계 올림픽 바이애슬론 – Korean

values: Biathlon ai XIX Giochi olimpici invernali – Italian

values: Biatlon a 2002. évi téli olimpiai játékokon – Hungarian

values:
interlanguage-link interwiki-hu
display: none;

values: Biatlon op de Olympische Winterspelen 2002 – Dutch

values:
interlanguage-link interwiki-nl
display: none;

values: 2002年ソルトレークシティオリンピックのバイアスロン競技 – Japanese

values: Skiskyting under Vinter-OL 2002 – Norwegian

values:
interlanguage-link interwiki-no
display: none;

values: Skiskyting under Vinter-OL 2002 – Norwegian Nynorsk

values:
interlanguage-link interwiki-nn
display: none;

values: Olympisch Winterspelen 2002/Biathlon – Low German

values:
interlanguage-link interwiki-nds
display: none;

values: Biathlon na Zimowych Igrzyskach Olimpijskich 2002 – Polish

values:
interlanguage-link interwiki-pl
display: none;

values: Biatlo nos Jogos Olímpicos de Inverno de 2002 – Portuguese

values: Биатлон на зимних Олимпийских играх 2002 – Russian

values: Biatlon na Zimskih olimpijskih igrah 2002 – Slovenian

values:
interlanguage-link interwiki-sl
display: none;

values: Ampumahiihto talviolympialaisissa 2002 – Finnish

values:
interlanguage-link interwiki-fi
display: none;

values: Skidskytte vid olympiska vinterspelen 2002 – Swedish

values:
interlanguage-link interwiki-sv
display: none;

values: Біатлон на зимових Олімпійських іграх 2002 – Ukrainian

values:
interlanguage-link interwiki-uk
display: none;

values: 2002年冬季奧林匹克運動會冬季兩項比賽 – Chinese

values: All languages (initial selection from common choices by you and others)

values: /static/images/wikimedia-button-1.5x.png 1.5x, /static/images/wikimedia-button-2x.png 2x

values: /static/images/poweredby_mediawiki_132x47.png 1.5x, /static/images/poweredby_mediawiki_176x62.png 2x

values:
suggestions
display: none; font-size: 13px;

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Biathlon_at_the_2002_Winter_Olympics rootpage-Biathlon_at_the_2002_Winter_Olympics skin-vector action-view


text:
Recursion (computer science)
From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about recursive approaches to solving problems. For proofs by recursion, see Mathematical induction. For recursion in computer science acronyms, see Recursive acronym § Computer-related examples.
Tree created using the Logo programming language and relying heavily on recursion. Each branch can be seen as a smaller version of a tree.
Programming paradigms
Action
Agent-oriented
Array-oriented
Automata-based
Concept
Concurrent computing
Relativistic programming
Data-driven
Declarative (contrast: Imperative)
Constraint
Constraint logic
Concurrent constraint logic
Dataflow
Flow-based
Cell-oriented (spreadsheets)
Reactive
Functional
Functional logic
Purely functional
Logic
Abductive logic
Answer set
Concurrent logic
Functional logic
Inductive logic
Dynamic
End-user programming
Event-driven
Service-oriented
Time-driven
Expression-oriented
Feature-oriented
Function-level (contrast: Value-level)
Generic
Imperative (contrast: Declarative)
Literate
Procedural
Language-oriented
Natural-language programming
Discipline-specific
Domain-specific
Grammar-oriented
Dialecting
Intentional
Metaprogramming
Automatic
Inductive programming
Reflective
Attribute-oriented
Homoiconic
Macro
Template
Policy-based
Non-structured (contrast: Structured)
Array
Nondeterministic
Parallel computing
Process-oriented
Point-free style
Concatenative
Probabilistic
Semantic
Structured (contrast: Non-structured)
Block-structured
Modular (contrast: Monolithic)
Object-oriented
Actor-based
Class-based
Concurrent
Prototype-based
By separation of concerns:
Aspect-oriented
Role-oriented
Subject-oriented
Recursive
Value-level (contrast: Function-level)
Quantum programming
v
t
e
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).[1] The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.[2]
"The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."[3]
Most computer programming languages support recursion by allowing a function to call itself within the program text. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory proves that these recursive-only languages are Turing complete; they are as computationally powerful as Turing complete imperative languages, meaning they can solve the same kinds of problems as imperative languages even without iterative control structures such as “while” and “for”.
Contents
[hide]
1 Recursive functions and algorithms
2 Recursive data types
2.1 Inductively defined data
2.2 Coinductively defined data and corecursion
3 Types of recursion
3.1 Single recursion and multiple recursion
3.2 Indirect recursion
3.3 Anonymous recursion
3.4 Structural versus generative recursion
4 Recursive programs
4.1 Recursive procedures
4.1.1 Factorial
4.1.2 Greatest common divisor
4.1.3 Towers of Hanoi
4.1.4 Binary search
4.2 Recursive data structures (structural recursion)
4.2.1 Linked lists
4.2.2 Binary trees
4.2.3 Filesystem traversal
5 Implementation issues
5.1 Wrapper function
5.2 Short-circuiting the base case
5.2.1 Depth-first search
5.3 Hybrid algorithm
6 Recursion versus iteration
6.1 Expressive power
6.2 Performance issues
6.3 Stack space
6.4 Multiply recursive problems
7 Tail-recursive functions
8 Order of execution
8.1 Function 1
8.2 Function 2 with swapped lines
9 Time-efficiency of recursive algorithms
9.1 Shortcut rule (master theorem)
10 See also
10.1 Recursive functions
11 Books
11.1 Monographs on recursive programming
11.2 Other
12 Notes and references
13 Further reading
14 External links
Recursive functions and algorithms[edit]
A common computer programming 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 solving sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as dynamic programming or memoization.
A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself). For example, the factorial function can be defined recursively by the equations 0! = 1 and, for all n > 0, n! = n(n − 1)!. Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".
The job of the recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached. (Functions that are not intended to terminate under normal circumstances—for example, some system and server processes—are an exception to this.) Neglecting to write a base case, or testing for it incorrectly, can cause an infinite loop.
For some functions (such as one that computes the series for e = 1/0! + 1/1! + 1/2! + 1/3! + ...) there is not an obvious base case implied by the input data; for these one may add a parameter (such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example is more naturally treated by co-recursion, where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the nth term (nth partial sum)".
Recursive data types[edit]
Many computer programs must process or generate an arbitrarily large quantity of data. Recursion is one technique for representing data whose exact size the programmer does not know: the programmer can specify this data with a self-referential definition. There are two types of self-referential definitions: inductive and coinductive definitions.
Further information: Algebraic data type
Inductively defined data[edit]
Main article: Recursive data type
An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, linked lists can be defined inductively (here, using Haskell syntax):
data ListOfStrings = EmptyList | Cons String ListOfStrings
The code above specifies a list of strings to be either empty, or a structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any (finite) number of strings.
Another example of inductive definition is the natural numbers (or positive integers):
A natural number is either 1 or n+1, where n is a natural number.
Similarly recursive definitions are often used to model the structure of expressions and statements in programming languages. Language designers often express grammars in a syntax such as Backus-Naur form; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition:
 <expr> ::= <number> | (<expr> * <expr>) | (<expr> + <expr>)
This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complex arithmetic expressions such as (5 * ((3 * 6) + 8)), with more than one product or sum operation in a single expression.
Coinductively defined data and corecursion[edit]
Main articles: Coinduction and Corecursion
A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size.
A coinductive definition of infinite streams of strings, given informally, might look like this:
A stream of strings is an object s such that:
 head(s) is a string, and
 tail(s) is a stream of strings.

This is very similar to an inductive definition of lists of strings; the difference is that this definition specifies how to access the contents of the data structure—namely, via the accessor functions head and tail—and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from.
Corecursion is related to coinduction, and can be used to compute particular instances of (possibly) infinite objects. As a programming technique, it is used most often in the context of lazy programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large (or infinitely precise) result, and a mechanism for taking a finite portion of that result. The problem of computing the first n prime numbers is one that can be solved with a corecursive program (e.g. here).
Types of recursion[edit]
Single recursion and multiple recursion[edit]
Recursion that only contains a single self-reference is known as single recursion, while recursion that contains multiple self-references is known as multiple recursion. Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include tree traversal, such as in a depth-first search.
Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.
Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively is multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, tracking at each step two successive values – see corecursion: examples. A more sophisticated example is using a threaded binary tree, which allows iterative tree traversal, rather than multiple recursion.
Indirect recursion[edit]
Main article: Mutual recursion
Most basic examples of recursion, and most of the examples presented here, demonstrate direct recursion, in which a function calls itself. Indirect recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if f calls f, that is direct recursion, but if f calls g which calls f, then that is indirect recursion of f. Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again.
Indirect recursion is also called mutual recursion, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, if f calls g and then g calls f, which in turn calls g again, from the point of view of f alone, f is indirectly recursing, while from the point of view of g alone, it is indirectly recursing, while from the point of view of both, f and g are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.
Anonymous recursion[edit]
Main article: Anonymous recursion
Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for anonymous functions, and is known as anonymous recursion.
Structural versus generative recursion[edit]
See also: Structural recursion
Some authors classify recursion as either "structural" or "generative". The distinction is related to where a recursive procedure gets the data that it works on, and how it processes that data:
[Functions that consume structured data] typically decompose their arguments into their immediate structural components and then process those components. If one of the immediate components belongs to the same class of data as the input, the function is recursive. For that reason, we refer to these functions as (STRUCTURALLY) RECURSIVE FUNCTIONS.[4]
Thus, the defining characteristic of a structurally recursive function is that the argument to each recursive call is the content of a field of the original input. Structural recursion includes nearly all tree traversals, including XML processing, binary tree creation and search, etc. By considering the algebraic structure of the natural numbers (that is, a natural number is either zero or the successor of a natural number), functions such as factorial may also be regarded as structural recursion.
Generative recursion is the alternative:
Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. HtDP (How To Design Programs) refers to this kind as generative recursion. Examples of generative recursion include: gcd, quicksort, binary search, mergesort, Newton's method, fractals, and adaptive integration.[5]
This distinction is important in proving termination of a function.
All structurally recursive functions on finite (inductively defined) data structures can easily be shown to terminate, via structural induction: intuitively, each recursive call receives a smaller piece of input data, until a base case is reached.
Generatively recursive functions, in contrast, do not necessarily feed smaller input to their recursive calls, so proof of their termination is not necessarily as simple, and avoiding infinite loops requires greater care. These generatively recursive functions can often be interpreted as corecursive functions – each step generates the new data, such as successive approximation in Newton's method – and terminating this corecursion requires that the data eventually satisfy some condition, which is not necessarily guaranteed.
In terms of loop variants, structural recursion is when there is an obvious loop variant, namely size or complexity, which starts off finite and decreases at each recursive step.
By contrast, generative recursion is when there is not such an obvious loop variant, and termination depends on a function, such as "error of approximation" that does not necessarily decrease to zero, and thus termination is not guaranteed without further analysis.
Recursive programs[edit]
Recursive procedures[edit]
Factorial[edit]
A classic example of a recursive procedure is the function used to calculate the factorial of a natural number:
fact  ( n ) = { 1 if n = 0 n ⋅ fact  ( n − 1 ) if n > 0 {\displaystyle \operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}}
Pseudocode (recursive):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ]
end factorial
The function can also be written as a recurrence relation:
b n = n b n − 1 {\displaystyle b_{n}=nb_{n-1}}
b 0 = 1 {\displaystyle b_{0}=1}
This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:
Computing the recurrence relation for n = 4:
b4 = 4 * b3
= 4 * (3 * b2) = 4 * (3 * (2 * b1)) = 4 * (3 * (2 * (1 * b0))) = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24
This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages:
Pseudocode (iterative):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. create new variable called running_total with a value of 1
2. begin loop 1. if n is 0, exit loop 2. set running_total to (running_total × n) 3. decrement n 4. repeat loop
3. return running_total
end factorial
The imperative code above is equivalent to this mathematical definition using an accumulator variable t:
fact  ( n ) = f a c t a c c  ( n , 1 ) f a c t a c c  ( n , t ) = { t if n = 0 f a c t a c c  ( n − 1 , n t ) if n > 0 {\displaystyle {\begin{array}{rcl}\operatorname {fact} (n)&=&\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&=&{\begin{cases}t&{\mbox{if }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{if }}n>0\\\end{cases}}\end{array}}}
The definition above translates straightforwardly to functional programming languages such as Scheme; this is an example of iteration implemented recursively.
Greatest common divisor[edit]
The Euclidean algorithm, which computes the greatest common divisor of two integers, can be written recursively.
Function definition:
gcd ( x , y ) = { x if y = 0 gcd ( y , remainder  ( x , y ) ) if y > 0 {\displaystyle \gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}}
Pseudocode (recursive):
function gcd is: input: integer x, integer y such that x > 0 and y >= 0
1. if y is 0, return x 2. otherwise, return [ gcd( y, (remainder of x/y) ) ]
end gcd
Recurrence relation for greatest common divisor, where x % y {\displaystyle x\%y} expresses the remainder of x / y {\displaystyle x/y} :
gcd ( x , y ) = gcd ( y , x % y ) {\displaystyle \gcd(x,y)=\gcd(y,x\%y)} if y ≠ 0 {\displaystyle y\neq 0}
gcd ( x , 0 ) = x {\displaystyle \gcd(x,0)=x}
Computing the recurrence relation for x = 27 and y = 9:
gcd(27, 9)   = gcd(9, 27% 9)
             = gcd(9, 0)
             = 9
Computing the recurrence relation for x = 111 and y = 259:
gcd(111, 259)   = gcd(259, 111% 259)
                = gcd(259, 111)
                = gcd(111, 259% 111)
                = gcd(111, 37)
                = gcd(37, 111% 37)
                = gcd(37, 0)
                = 37
The recursive program above is tail-recursive; it is equivalent to an iterative algorithm, and the computation shown above shows the steps of evaluation that would be performed by a language that eliminates tail calls. Below is a version of the same algorithm using explicit iteration, suitable for a language that does not eliminate tail calls. By maintaining its state entirely in the variables x and y and using a looping construct, the program avoids making recursive calls and growing the call stack.
Pseudocode (iterative):
function gcd is:
input: integer x, integer y such that x >= y and y >= 0
1. create new variable called remainder
2. begin loop 1. if y is zero, exit loop 2. set remainder to the remainder of x/y 3. set x to y 4. set y to remainder 5. repeat loop
3. return x
end gcd
The iterative algorithm requires a temporary variable, and even given knowledge of the Euclidean algorithm it is more difficult to understand the process by simple inspection, although the two algorithms are very similar in their steps.
Towers of Hanoi[edit]
Towers of Hanoi
Main article: Towers of Hanoi
The Towers of Hanoi is a mathematical puzzle whose solution illustrates recursion.[6][7] There are three pegs which can hold stacks of disks of different diameters. A larger disk may never be stacked on top of a smaller. Starting with n disks on one peg, they must be moved to another peg one at a time. What is the smallest number of steps to move the stack?
Function definition:
hanoi  ( n ) = { 1 if n = 1 2 ⋅ hanoi  ( n − 1 ) + 1 if n > 1 {\displaystyle \operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}}
Recurrence relation for hanoi:
h n = 2 h n − 1 + 1 {\displaystyle h_{n}=2h_{n-1}+1}
h 1 = 1 {\displaystyle h_{1}=1}
Computing the recurrence relation for n = 4:
hanoi(4)     = 2*hanoi(3) + 1
             = 2*(2*hanoi(2) + 1) + 1
             = 2*(2*(2*hanoi(1) + 1) + 1) + 1
             = 2*(2*(2*1 + 1) + 1) + 1
             = 2*(2*(3) + 1) + 1
             = 2*(7) + 1
             = 15

Example implementations:
Pseudocode (recursive):
function hanoi is:
input: integer n, such that n >= 1
1. if n is 1 then return 1
2. return [2 * [call hanoi(n-1)] + 1]
end hanoi
Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.[8]
An explicit formula for Towers of Hanoi:
h1 = 1 = 21 - 1 h2 = 3 = 22 - 1 h3 = 7 = 23 - 1 h4 = 15 = 24 - 1 h5 = 31 = 25 - 1 h6 = 63 = 26 - 1 h7 = 127 = 27 - 1

In general:
hn = 2n - 1, for all n >= 1
Binary search[edit]
The binary search algorithm is a method of searching a sorted array for a single element by cutting the array in half with each recursive pass. The trick is to pick a midpoint near the center of the array, compare the data at that point with the data being searched and then responding to one of three possible conditions: the data is found at the midpoint, the data at the midpoint is greater than the data being searched for, or the data at the midpoint is less than the data being searched for.
Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new (and smaller) array. Typically the array's size is adjusted by manipulating a beginning and ending index. The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.
Example implementation of binary search in C:
 /* Call binary_search with proper initial conditions. INPUT: data is an array of integers SORTED in ASCENDING order, toFind is the integer to search for, count is the total number of elements in the array OUTPUT: result of binary_search */ int search(int *data, int toFind, int count) { // Start = 0 (beginning index) // End = count - 1 (top index) return binary_search(data, toFind, 0, count-1); } /* Binary Search Algorithm. INPUT: data is a array of integers SORTED in ASCENDING order, toFind is the integer to search for, start is the minimum array index, end is the maximum array index OUTPUT: position of the integer toFind within array data, -1 if not found */ int binary_search(int *data, int toFind, int start, int end) { //Get the midpoint. int mid = start + (end - start)/2; //Integer division //Stop condition. if (start > end) return -1; else if (data[mid] == toFind) //Found? return mid; else if (data[mid] > toFind) //Data is greater than toFind, search lower half return binary_search(data, toFind, start, mid-1); else //Data is less than toFind, search upper half return binary_search(data, toFind, mid+1, end); }
Recursive data structures (structural recursion)[edit]
Main article: Recursive data type
An important application of recursion in computer science is in defining dynamic data structures such as lists and trees. Recursive data structures can dynamically grow to a theoretically infinite size in response to runtime requirements; in contrast, the size of a static array must be set at compile time.
"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms."[9]
The examples in this section illustrate what is known as "structural recursion". This term refers to the fact that the recursive procedures are acting on data that is defined recursively.
As long as a programmer derives the template from a data definition, functions employ structural recursion. That is, the recursions in a function's body consume some immediate piece of a given compound value.[5]
Linked lists[edit]
Main article: Linked list
Below is a C definition of a linked list node structure. Notice especially how the node is defined in terms of itself. The "next" element of struct node is a pointer to another struct node, effectively creating a list type.
struct node { int data; // some integer data struct node *next; // pointer to another struct node };
Because the struct node data structure is defined recursively, procedures that operate on it can be implemented naturally as recursive procedures. The list_print procedure defined below walks down the list until the list is empty (i.e., the list pointer has a value of NULL). For each node it prints the data element (an integer). In the C implementation, the list remains unchanged by the list_print procedure.
void list_print(struct node *list) { if (list != NULL) // base case { printf ("%d ", list->data); // print integer data followed by a space list_print (list->next); // recursive call on the next node } }
Binary trees[edit]
Main article: Binary tree
Below is a simple definition for a binary tree node. Like the node for linked lists, it is defined in terms of itself, recursively. There are two self-referential pointers: left (pointing to the left sub-tree) and right (pointing to the right sub-tree).
struct node { int data; // some integer data struct node *left; // pointer to the left subtree struct node *right; // point to the right subtree };
Operations on the tree can be implemented using recursion. Note that because there are two self-referencing pointers (left and right), tree operations may require two recursive calls:
// Test if tree_node contains i; return 1 if so, 0 if not. int tree_contains(struct node *tree_node, int i) { if (tree_node == NULL) return 0; // base case else if (tree_node->data == i) return 1; else return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i); }
At most two recursive calls will be made for any given call to tree_contains as defined above.
// Inorder traversal: void tree_print(struct node *tree_node) { if (tree_node != NULL) { // base case tree_print(tree_node->left); // go left printf("%d ", tree_node->data); // print the integer followed by a space tree_print(tree_node->right); // go right } }
The above example illustrates an in-order traversal of the binary tree. A Binary search tree is a special case of the binary tree where the data elements of each node are in order.
Filesystem traversal[edit]
Since the number of files in a filesystem may vary, recursion is the only practical way to traverse and thus enumerate its contents. Traversing a filesystem is very similar to that of tree traversal, therefore the concepts behind tree traversal are applicable to traversing a filesystem. More specifically, the code below would be an example of a preorder traversal of a filesystem.
import java.io.*; public class FileSystem { public static void main (String [] args) { traverse (); } /** * Obtains the filesystem roots * Proceeds with the recursive filesystem traversal */ private static void traverse () { File [] fs = File.listRoots (); for (int i = 0; i < fs.length; i++) { if (fs[i].isDirectory () && fs[i].canRead ()) { rtraverse (fs[i]); } } } /** * Recursively traverse a given directory * * @param fd indicates the starting point of traversal */ private static void rtraverse (File fd) { File [] fss = fd.listFiles (); for (int i = 0; i < fss.length; i++) { System.out.println (fss[i]); if (fss[i].isDirectory () && fss[i].canRead ()) { rtraverse (fss[i]); } } } }
This code blends the lines, at least somewhat, between recursion and iteration. It is, essentially, a recursive implementation, which is the best way to traverse a filesystem. It is also an example of direct and indirect recursion. The method "rtraverse" is purely a direct example; the method "traverse" is the indirect, which calls "rtraverse." This example needs no "base case" scenario due to the fact that there will always be some fixed number of files or directories in a given filesystem.
Implementation issues[edit]
In actual implementation, rather than a pure recursive function (single check for base case, otherwise recursive step), a number of modifications may be made, for purposes of clarity or efficiency. These include:
Wrapper function (at top)
Short-circuiting the base case, aka "Arm's-length recursion" (at bottom)
Hybrid algorithm (at bottom) – switching to a different algorithm once data is small enough
On the basis of elegance, wrapper functions are generally approved, while short-circuiting the base case is frowned upon, particularly in academia. Hybrid algorithms are often used for efficiency, to reduce the overhead of recursion in small cases, and arm's-length recursion is a special case of this.
Wrapper function[edit]
A wrapper function is a function that is directly called but does not recurse itself, instead calling a separate auxiliary function which actually does the recursion.
Wrapper functions can be used to validate parameters (so the recursive function can skip these), perform initialization (allocate memory, initialize variables), particularly for auxiliary variables such as "level of recursion" or partial computations for memoization, and handle exceptions and errors. In languages that support nested functions, the auxiliary function can be nested inside the wrapper function and use a shared scope. In the absence of nested functions, auxiliary functions are instead a separate function, if possible private (as they are not called directly), and information is shared with the wrapper function by using pass-by-reference.
Short-circuiting the base case[edit]
Short-circuiting the base case, also known as arm's-length recursion, consists of checking the base case before making a recursive call – i.e., checking if the next call will be the base case, instead of calling and then checking for the base case. Short-circuiting is particularly done for efficiency reasons, to avoid the overhead of a function call that immediately returns. Note that since the base case has already been checked for (immediately before the recursive step), it does not need to be checked for separately, but one does need to use a wrapper function for the case when the overall recursion starts with the base case itself. For example, in the factorial function, properly the base case is 0! = 1, while immediately returning 1 for 1! is a short-circuit, and may miss 0; this can be mitigated by a wrapper function.
Short-circuiting is primarily a concern when many base cases are encountered, such as Null pointers in a tree, which can be linear in the number of function calls, hence significant savings for O(n) algorithms; this is illustrated below for a depth-first search. Short-circuiting on a tree corresponds to considering a leaf (non-empty node with no children) as the base case, rather than considering an empty node as the base case. If there is only a single base case, such as in computing the factorial, short-circuiting provides only O(1) savings.
Conceptually, short-circuiting can be considered to either have the same base case and recursive step, only checking the base case before the recursion, or it can be considered to have a different base case (one step removed from standard base case) and a more complex recursive step, namely "check valid then recurse", as in considering leaf nodes rather than Null nodes as base cases in a tree. Because short-circuiting has a more complicated flow, compared with the clear separation of base case and recursive step in standard recursion, it is often considered poor style, particularly in academia.
Depth-first search[edit]
A basic example of short-circuiting is given in depth-first search (DFS) of a binary tree; see binary trees section for standard recursive discussion.
The standard recursive algorithm for a DFS is:
base case: If current node is Null, return false
recursive step: otherwise, check value of current node, return true if match, otherwise recurse on children
In short-circuiting, this is instead:
check value of current node, return true if match,
otherwise, on children, if not Null, then recurse.
In terms of the standard steps, this moves the base case check before the recursive step. Alternatively, these can be considered a different form of base case and recursive step, respectively. Note that this requires a wrapper function to handle the case when the tree itself is empty (root node is Null).
In the case of a perfect binary tree of height h, there are 2h+1−1 nodes and 2h+1 Null pointers as children (2 for each of the 2h leaves), so short-circuiting cuts the number of function calls in half in the worst case.
In C, the standard recursive algorithm may be implemented as:
bool tree_contains(struct node *tree_node, int i) { if (tree_node == NULL) return false; // base case else if (tree_node->data == i) return true; else return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i); }
The short-circuited algorithm may be implemented as:
// Wrapper function to handle empty tree bool tree_contains(struct node *tree_node, int i) { if (tree_node == NULL) return false; // empty tree else return tree_contains_do(tree_node, i); // call auxiliary function } // Assumes tree_node != NULL bool tree_contains_do(struct node *tree_node, int i) { if (tree_node->data == i) return true; // found else // recurse return (tree_node->left && tree_contains_do(tree_node->left, i)) || (tree_node->right && tree_contains_do(tree_node->right, i)); }
Note the use of short-circuit evaluation of the Boolean && (AND) operators, so that the recursive call is only made 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 bool, so the overall expression evaluates to a bool. 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[edit]
Recursive algorithms are often inefficient for small data, due to the overhead of repeated function calls and returns. For this reason efficient implementations of recursive algorithms often start with the recursive algorithm, but then switch to a different algorithm when the input becomes small. An important example is merge sort, which is often implemented by switching to the non-recursive insertion sort when the data is sufficiently small, as in the tiled merge sort. Hybrid recursive algorithms can often be further refined, as in Timsort, derived from a hybrid merge sort/insertion sort.
Recursion versus iteration[edit]
Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with 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 languages recursion is preferred, with tail recursion optimization leading to little overhead, and sometimes explicit iteration is not available.
Compare the templates to compute xn defined by xn = f(n, xn-1) from xbase:
function recursive(n)
    if n==base
        return xbase else return f(n, recursive(n-1))
function iterative(n)
    x = xbase for i = n downto base x = f(i, x) return x
For imperative language the overhead is to define the function, for functional language the overhead is to define the accumulator variable x.
For example, the factorial function may be implemented iteratively in C by assigning to an loop index variable and accumulator variable, rather than passing arguments and returning values by recursion:
unsigned int factorial(unsigned int n) { unsigned int product = 1; // empty product is 1 while (n) { product *= n; --n; } return product; }
Expressive power[edit]
Most programming languages in use today allow the direct specification of recursive functions and procedures. When such a function is called, the program's runtime environment keeps track of the various instances of the function (often using a call stack, although other methods may be used). Every recursive function can be transformed into an iterative function by replacing recursive calls with iterative control constructs and simulating the call stack with a stack explicitly managed by the program.[10][11]
Conversely, all iterative functions and procedures that can be evaluated by a computer (see Turing completeness) can be expressed in terms of recursive functions; iterative control constructs such as while loops and do loops are routinely rewritten in recursive form in functional languages.[12][13] However, in practice this rewriting depends on tail call elimination, which is not a feature of all languages. C, Java, and Python are notable mainstream languages in which all function calls, including tail calls, may cause stack allocation that would not occur with the use of looping constructs; in these languages, a working iterative program rewritten in recursive form may overflow the call stack, although tail call elimination may be a feature that is not covered by a language's specification, and different implementations of the same language may differ in tail call elimination capabilities.
Performance issues[edit]
In languages (such as C and 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 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[edit]
In some programming languages, the maximum size of the call stack is much less than the space available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms. Consequently, these languages sometimes place a limit on the depth of recursion to avoid stack overflows; Python is one such language.[14] Note the caveat below regarding the special case of tail recursion.
Multiply recursive problems[edit]
Multiply recursive problems are inherently recursive, because of prior state they need to track. One example is tree traversal as in depth-first search; contrast with list traversal and linear search in a list, which is singly recursive and thus naturally iterative. Other examples include divide-and-conquer algorithms such as Quicksort, and functions such as the Ackermann function. All of these algorithms can be implemented iteratively with the help of an explicit stack, but the programmer effort involved in managing the stack, and the complexity of the resulting program, arguably outweigh any advantages of the iterative solution.
Tail-recursive functions[edit]
Tail-recursive functions are functions in which all recursive calls are tail calls and hence do not build up any deferred operations. For example, the gcd function (shown again below) is tail-recursive. In contrast, the factorial function (also below) is not tail-recursive; because its recursive call is not in tail position, it builds up deferred multiplication operations that must be performed after the final recursive call completes. With a compiler or interpreter that treats tail-recursive calls as jumps rather than function calls, a tail-recursive function such as gcd will execute using constant space. Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops.
Tail recursion:
Augmenting recursion:
//INPUT: Integers x, y such that x >= y and y > 0 int gcd(int x, int y) { if (y == 0) return x; else return gcd(y, x % y); }
//INPUT: n is an Integer such that n >= 0 int fact(int n) { if (n == 0) return 1; else return n * fact(n - 1); }
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[edit]
In the simple 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. Consider this example:
Function 1[edit]
void recursiveFunction(int num) { printf("%d\n", num); if (num < 4) recursiveFunction(num + 1); }
Function 2 with swapped lines[edit]
void recursiveFunction(int num) { if (num < 4) recursiveFunction(num + 1); printf("%d\n", num); }
Time-efficiency of recursive algorithms[edit]
The time efficiency of recursive algorithms can be expressed in a recurrence relation of Big O notation. They can (usually) then be simplified into a single Big-Oh term.
Shortcut rule (master theorem)[edit]
Main article: Master theorem (analysis of algorithms)
If the time-complexity of the function is in the form
T ( n ) = a ⋅ T ( n / b ) + f ( n ) {\displaystyle T(n)=a\cdot T(n/b)+f(n)}
Then the Big-Oh of the time-complexity is thus:
If f ( n ) = O ( n log b  a − ϵ ) {\displaystyle f(n)=O(n^{\log _{b}a-\epsilon })} for some constant ϵ > 0 {\displaystyle \epsilon >0} , then T ( n ) = Θ ( n log b  a ) {\displaystyle T(n)=\Theta (n^{\log _{b}a})}
If f ( n ) = Θ ( n log b  a ) {\displaystyle f(n)=\Theta (n^{\log _{b}a})} , then T ( n ) = Θ ( n log b  a log  n ) {\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)}
If f ( n ) = Ω ( n log b  a + ϵ ) {\displaystyle f(n)=\Omega (n^{\log _{b}a+\epsilon })} for some constant ϵ > 0 {\displaystyle \epsilon >0} , and if a ⋅ f ( n / b ) ≤ c ⋅ f ( n ) {\displaystyle a\cdot f(n/b)\leq c\cdot f(n)} for some constant c < 1 and all sufficiently large n, then T ( n ) = Θ ( f ( n ) ) {\displaystyle T(n)=\Theta (f(n))}
where a represents the number of recursive calls at each level of recursion, 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 f (n) represents the work the function does independent of any recursion (e.g. partitioning, recombining) at each level of recursion.
See also[edit]
Functional programming
Hierarchical and recursive queries in SQL
Kleene–Rosser paradox
Open recursion
Recursion
Sierpiński curve
Recursive functions[edit]
McCarthy 91 function
μ-recursive functions
Primitive recursive functions
Tak (function)
Books[edit]
Monographs on recursive programming[edit]
Practicing Recursion in Java, I. Pevac (CreateSpace Independent Publishing Platform, 2016)
Thinking Recursively with Java, E. S. Roberts (Wiley, 2006)
Recursion via Pascal, J. S. Rohl (Cambridge University Press, 1984)
Other[edit]
Walls and Mirrors, Paul Helman and Robert Veroff
Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay Sussman, and Julie Sussman (MIT Press, 1996)
Notes and references[edit]
Jump up ^ Graham, Ronald; Donald Knuth; Oren Patashnik (1990). Concrete Mathematics. Chapter 1: Recurrent Problems.
Jump up ^ Epp, Susanna (1995). Discrete Mathematics with Applications (2nd ed.). p. 427.
Jump up ^ Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126.
Jump up ^ Felleisen, Matthias; Robert Bruce Findler; Matthew Flatt; Shriram Krishnamurthi (2001). How to Design Programs: An Introduction to Computing and Programming. Cambridge, MASS: MIT Press. p. art V "Generative Recursion".
^ Jump up to: a b Felleisen, Matthias (2002). "Developing Interactive Web Programs". In Jeuring, Johan. Advanced Functional Programming: 4th International School. Oxford, UK: Springer. p. 108.
Jump up ^ Graham, Ronald; Donald Knuth; Oren Patashnik (1990). Concrete Mathematics. Chapter 1, Section 1.1: The Tower of Hanoi.
Jump up ^ Epp, Susanna (1995). Discrete Mathematics with Applications (2nd ed.). pp. 427–430: The Tower of Hanoi.
Jump up ^ Epp, Susanna (1995). Discrete Mathematics with Applications (2nd ed.). pp. 447–448: An Explicit Formula for the Tower of Hanoi Sequence.
Jump up ^ Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 127.
Jump up ^ Hetland, Magnus Lie (2010), Python Algorithms: Mastering Basic Algorithms in the Python Language, Apress, p. 79, ISBN 9781430232384 .
Jump up ^ Drozdek, Adam (2012), Data Structures and Algorithms in C++ (4th ed.), Cengage Learning, p. 197, ISBN 9781285415017 .
Jump up ^ Shivers, Olin. "The Anatomy of a Loop - A story of scope and control" (PDF). Georgia Institute of Technology. Retrieved 2012-09-03.
Jump up ^ Lambda the Ultimate. "The Anatomy of a Loop". Lambda the Ultimate. Retrieved 2012-09-03.
Jump up ^ "27.1. sys — System-specific parameters and functions — Python v2.7.3 documentation". Docs.python.org. Retrieved 2012-09-03.
Further reading[edit]
Dijkstra, Edsger W. (1960). "Recursive Programming". Numerische Mathematik. 2 (1): 312–318. doi:10.1007/BF01386232.
External links[edit]
Jonathan Bartlett: "Mastering Recursive Programming"
David S. Touretzky: "Common Lisp: A Gentle Introduction to Symbolic Computation"
Matthias Felleisen: "How To Design Programs: An Introduction to Computing and Programming"
Owen L. Astrachan: "Big-Oh for Recursive Functions: Recurrence Relations"
Retrieved from "https://en.wikipedia.org/w/index.php?title=Recursion_(computer_science)&oldid=820421884"
Categories:
Theoretical computer science
Recursion
Computability theory
Programming idioms
Subroutines
Hidden categories:
Articles with example pseudocode
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
Languages
العربية
Boarisch
Català
Čeština
Deutsch
Español
فارسی
Français
한국어
Հայերեն
Italiano
Қазақша
Nederlands
日本語
Português
Русский
Simple English
Slovenčina
Српски / srpski
Suomi
Svenska
Українська
Tiếng Việt
中文
Edit links
This page was last edited on 14 January 2018, at 17:37.
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

key: html

type: local

value: div

attrs: id class

values: mw-page-base noprint

values: mw-head-base noprint

value: a

attrs: id class lang

values: firstHeading firstHeading en

values: siteSub noprint

values: jump-to-nav mw-jump

attrs: href title

attrs: role class

values:
note
hatnote navigation-not-searchable

value: img

attrs: alt src width height class srcset data-file-width data-file-height

attrs: href class title

attrs: class style

value: th

value: tr

value: li

values: float:right;clear:right;width:22.0em;margin:0 0 1.0em 1.0em;background:#f9f9f9;border:1px solid #aaa;padding:0.2em;border-spacing:0.4em 0;text-align:center;line-height:1.4em;font-size:88%

values:
/wiki/Function_(computer_science)
mw-redirect
Function (computer science)

values:
/wiki/Functional_languages
mw-redirect
Functional languages

values: Edit section: Recursive functions and algorithms

values:
/wiki/Divide-and-conquer_method
mw-redirect
Divide-and-conquer method

values:
/wiki/Trivial_(mathematics)
mw-redirect
Trivial (mathematics)

values:
/wiki/Daemon_(computer_software)
mw-redirect
Daemon (computer software)

values:
/wiki/Self_reference
mw-redirect
Self reference

values:
/wiki/Natural_numbers
mw-redirect
Natural numbers

values:
/wiki/Expression_(programming)
mw-redirect
Expression (programming)

values:
/wiki/Statement_(programming)
mw-redirect
Statement (programming)

values:
/wiki/Backus-Naur_form
mw-redirect
Backus-Naur form

values: Edit section: Coinductively defined data and corecursion

values:
/wiki/Prime_numbers
mw-redirect
Prime numbers

values: Edit section: Single recursion and multiple recursion

values: Edit section: Structural versus generative recursion

values:
/wiki/Structural_recursion
mw-redirect
Structural recursion

values:
/wiki/How_to_design_programs
mw-redirect
How to design programs

values:
/wiki/Binary_search
mw-redirect
Binary search

values:
/wiki/Infinite_loops
mw-redirect
Infinite loops

attrs: columnalign rowspacing columnspacing displaystyle

values: vertical-align: -2.505ex; width:36.618ex; height:6.176ex;

values: vertical-align: -0.671ex; width:11.026ex; height:2.509ex;

values: vertical-align: -0.671ex; width:6.313ex; height:2.509ex;

values: vertical-align: -4.171ex; width:48.127ex; height:9.509ex;

values:
/wiki/Functional_programming_language
mw-redirect
Functional programming language

values: vertical-align: -2.505ex; width:47.12ex; height:6.176ex;

values: vertical-align: -0.671ex; width:4.421ex; height:2.676ex;

values: vertical-align: -0.838ex; width:3.648ex; height:2.843ex;

values: vertical-align: -0.838ex; width:23.821ex; height:2.843ex;

values: vertical-align: -0.838ex; width:5.416ex; height:2.676ex;

values: vertical-align: -0.838ex; width:13.251ex; height:2.843ex;

values:
/wiki/Towers_of_Hanoi
mw-redirect
Towers of Hanoi

values: vertical-align: -2.505ex; width:43.879ex; height:6.176ex;

values: vertical-align: -0.671ex; width:15.479ex; height:2.509ex;

values: vertical-align: -0.671ex; width:6.654ex; height:2.509ex;

values: Edit section: Recursive data structures (structural recursion)

values:
/wiki/Preorder_traversal
mw-redirect
Preorder traversal

values: Edit section: Short-circuiting the base case

values:
/wiki/Perfect_binary_tree
mw-redirect
Perfect binary tree

values:
/wiki/Tiled_merge_sort
mw-redirect
Tiled merge sort

values: Edit section: Recursion versus iteration

values:
/wiki/Runtime_environment
mw-redirect
Runtime environment

values:
/wiki/Control_operator#Loops
mw-redirect
Control operator

values:
/wiki/Stack_(data_structure)
mw-redirect
Stack (data structure)

values:
/wiki/Functional_language
mw-redirect
Functional language

values:
/wiki/Tail_call_elimination
mw-redirect
Tail call elimination

values:
/wiki/Heap_(programming)
mw-redirect
Heap (programming)

values:
/wiki/Tail_recursion
mw-redirect
Tail recursion

values: Edit section: Multiply recursive problems

values:
/wiki/Divide-and-conquer_algorithm
mw-redirect
Divide-and-conquer algorithm

attrs: alt src width height srcset data-file-width data-file-height

values: Edit section: Function 2 with swapped lines

values: Edit section: Time-efficiency of recursive algorithms

values: Edit section: Shortcut rule (master theorem)

values: vertical-align: -0.838ex; width:25.171ex; height:2.843ex;

values: {\displaystyle f(n)=O(n^{\log _{b}a-\epsilon })}

values: vertical-align: -0.838ex; width:18.832ex; height:3.176ex;

values: vertical-align: -0.338ex; width:5.205ex; height:2.176ex;

values: {\displaystyle T(n)=\Theta (n^{\log _{b}a})}

values: vertical-align: -0.838ex; width:17.278ex; height:3.176ex;

values: {\displaystyle f(n)=\Theta (n^{\log _{b}a})}

values: vertical-align: -0.838ex; width:16.92ex; height:3.176ex;

values: {\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)}

values: vertical-align: -0.838ex; width:22.419ex; height:3.176ex;

values: {\displaystyle f(n)=\Omega (n^{\log _{b}a+\epsilon })}

values: vertical-align: -0.838ex; width:18.736ex; height:3.176ex;

values: {\displaystyle a\cdot f(n/b)\leq c\cdot f(n)}

values: vertical-align: -0.838ex; width:19.819ex; height:2.843ex;

values: vertical-align: -0.838ex; width:16.039ex; height:2.843ex;

values: Hierarchical and recursive queries in SQL

values:
/wiki/Open_recursion
mw-redirect
Open recursion

values: Edit section: Monographs on recursive programming

values: Structure and Interpretation of Computer Programs

values: -moz-column-width: 30em; -webkit-column-width: 30em; column-width: 30em; list-style-type: decimal;

values:
nofollow
external text
//doi.org/10.1007%2FBF01386232

values:
nofollow
http://www.cs.cmu.edu/~dst/LispBook/
external text

values:
nofollow
http://www.htdp.org/2003-09-26/Book/
external text

values: Category:Articles with example pseudocode

values: Discussion about edits from this IP address [ctrl-alt-n]

values: A list of edits made from this IP address [ctrl-alt-y]

values: You are encouraged to create an account and log in; however, it is not mandatory

values: You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]

values:
/wiki/Recursion_(computer_science)
View the content page [ctrl-alt-c]
c

values: Discussion about the content page [ctrl-alt-t]

values: p-namespaces navigation vectorTabs p-namespaces-label

values:
p-variants
navigation
vectorMenu emptyPortlet
p-variants-label

values: Past revisions of this page [ctrl-alt-h]

values: p-views navigation vectorTabs p-views-label

values:
p-cactions
navigation
vectorMenu emptyPortlet
p-cactions-label

values:
mw-wiki-logo
/wiki/Main_Page
Visit the main page

values:
/wiki/Main_Page
Visit the main page [ctrl-alt-z]
z

values: Featured content – the best of Wikipedia

values: Find background information on current events

values:
/wiki/Special:Random
Load a random article [ctrl-alt-x]
x

values: portal navigation p-navigation p-navigation-label

values: Guidance on how to use and edit Wikipedia

values: About the project, what you can do, where to find things

values: A list of recent changes in the wiki [ctrl-alt-r]

values: portal navigation p-interaction p-interaction-label

values: List of all English Wikipedia pages containing links to this page [ctrl-alt-j]

values: Recent changes in pages linked from this page [ctrl-alt-k]

values:
/wiki/Wikipedia:File_Upload_Wizard
Upload files [ctrl-alt-u]
u

values: A list of all special pages [ctrl-alt-q]

values: Permanent link to this revision of the page

values: Link to connected data repository item [ctrl-alt-g]

values: Printable version of this page [ctrl-alt-p]

values:
uls-settings-trigger
Language settings
0
button
true

values: استدعاء ذاتي (علم الحاسوب) – Arabic

values: Recursión (ciencias de computación) – Spanish

values: توابع بازگشتی – Persian

values: Կրկնարկում (ծրագրավորում) – Armenian

values: Рекурсивті функция – Kazakh

values: Recursividade (ciência da computação) – Portuguese

values: Рекурсивная функция – Russian

values: Рекурзија (компјутерске науке) – Serbian

values: Рекурсія (програмування) – Ukrainian

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Recursion_computer_science rootpage-Recursion_computer_science skin-vector action-view