25,161
edits
Changes
Created page with "'''Home * Programming * Algorithms * Recursion''' FILE:Bottrop_Halde_Beckstraße_Tetraeder.JPG|border|right|thumb|[https://en.wikipedia.org/wiki/Tetra..."
'''[[Main Page|Home]] * [[Programming]] * [[Algorithms]] * Recursion'''
[[FILE:Bottrop_Halde_Beckstraße_Tetraeder.JPG|border|right|thumb|[https://en.wikipedia.org/wiki/Tetrahedron_in_Bottrop Tetrahedron in Bottrop] <ref>[https://en.wikipedia.org/wiki/Tetrahedron Tetrahedron] in [https://en.wikipedia.org/wiki/Bottrop Bottrop], [https://en.wikipedia.org/wiki/North_Rhine-Westphalia North Rhine-Westphalia], Germany, part of [[Arts#IndustrialHeritageTrail|The Industrial Heritage Trail]], [https://commons.wikimedia.org/wiki/File:Bottrop_-_Halde_Beckstra%C3%9Fe_-_Tetraeder_03_ies.jpg Image] by [[Gerd Isenberg]], April 08, 2017. The design is reminiscent of the [https://en.wikipedia.org/wiki/Sierpinski_triangle#Analogues_in_higher_dimensions Sierpinski tetrix] : placing four half-size tetrahedra corner to corner and adding an octahedron in the middle, a full-size tetrahedron is formed; this process can be repeated recursively to form larger and larger tetrahedra, from [https://en.wikipedia.org/wiki/Tetrahedron_in_Bottrop Tetrahedron in Bottrop from Wikipedia], [https://commons.wikimedia.org/wiki/Category:Tetraeder_Bottrop Category:Tetraeder Bottrop] - [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [http://www.halden.ruhr/halden.html Halden im Ruhrgebiet] (German)</ref> ]]
'''Recursion''' is a technique to define a function, or process of repeating objects, in a [https://en.wikipedia.org/wiki/Self-similarity self-similar] way. In computer science it is a method or algorithm where the solution to a problem depends on solutions to smaller instances of the same problem.
=Sample=
In the [https://en.wikipedia.org/wiki/Tower_of_Hanoi Tower of Hanoi] puzzle to move N disks from peg A to C can be reduced to three sub problems:
# Moving N-1 disks from peg A to intermediate peg B
# Move the largest Disk N from peg A to target C
# Finally move the N-1 parked disks from B to C
: [[FILE:Tower of Hanoi.gif|none|border|text-bottom|link=https://de.wikipedia.org/wiki/T%C3%BCrme_von_Hanoi]]
=Recursive Definitions=
A [https://en.wikipedia.org/wiki/Recursive_definition recursive definition] of an object refers inductive terms of itself. A function set need to specify the function for some discrete values like zero, one or empty (base case), and to reduce all other cases by [https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm divide and conquer] toward the base case. [https://en.wikipedia.org/wiki/Recurrence_relations Recurrence relation] is an equation that recursively defines a sequence of symbols or numbers <ref>[https://en.wikipedia.org/wiki/Hofstadter_sequence Hofstadter sequence from Wikipedia]</ref>.
''Some more or less computer chess related examples ...''
==PGN Syntax==
The [https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form BNF]-like [https://en.wikipedia.org/wiki/Syntax Syntax] of the [[Portable Game Notation]] by [[Steven Edwards]] contains some recursive definitions, most [https://en.wikipedia.org/wiki/Tail_recursion tail recursion] for iteration of games, and tag-pairs and elements inside a game <ref>[http://www.thechessdrum.net/PGN_Reference.txt Standard: Portable Game Notation Specification and Implementation Guide] by [[Steven Edwards]], 18: Formal syntax</ref> :
<pre>
<PGN-database> ::= <PGN-game> <PGN-database>
<empty>
<tag-section> ::= <tag-pair> <tag-section>
<empty>
<element-sequence> ::= <element> <element-sequence>
<recursive-variation> <element-sequence>
<empty>
<recursive-variation> ::= ( <element-sequence> )
</pre>
==Index of PV-Array==
An index of a [[Triangular PV-Table]] may be defined recursively that way ...
index(0) = 0
index(ply+1) = index(ply) + N - ply
...which can be trivially transformed from [https://en.wikipedia.org/wiki/Tail_recursion tail recursion] to [https://en.wikipedia.org/wiki/Iteration iteration], finally applying a [https://en.wikipedia.org/wiki/Summation summation]:
index(ply) = ½ ply (2N + 1 - ply )
==Population Count==
The recursive definition of [[Population Count|population count]] (number of one-bits in a computer word i. e. a [[Bitboards|bitboard]]) can be transformed to iteration as well, but lacks an arithmetical sum-formula:
popcnt(0) = 0
popcnt(n) = popcnt(n ÷ 2) + (n mod 2)
<span id="InfixExpression"></span>
==Infix Expression==
[https://en.wikipedia.org/wiki/Syntax_%28programming_languages%29 Formal syntax] of [[Languages|
programming languages]] likely contain recursive definitions, i. e. [https://en.wikipedia.org/wiki/Parsing parsing] of arithmetical (and/or boolean) [https://en.wikipedia.org/wiki/Infix_notation infix notation] therefor implies indirect recursion, as demonstrated in following example with constants and [https://en.wikipedia.org/wiki/Elementary_arithmetic elementary arithmetic] only, which might even evaluated at [https://en.wikipedia.org/wiki/Compile_time compile time]:
''[https://en.wikipedia.org/wiki/Terminal_and_nonterminal_symbols Terminal and none terminal symbols] of a variant of [https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form BNF] below are embedded in ' ' resp. < >.''
<pre>
<expression> ::= <term> [ {'+' | '-'} <term> ]...
<term> ::= <factor> [ {'*' | '/'} <factor> ]...
<factor> ::= <constant> | '(' <expression> ')'
</pre>
=Implementation=
In [https://en.wikipedia.org/wiki/Procedural_programming procedual programming], recursion is done by a procedure aka [https://en.wikipedia.org/wiki/Subroutine subroutine], method or function, which calls itself if no base case is determined, utilizing the [[Stack|processor stack]]. One has to take care the nesting is not too deep or infinite, which yields in a [https://en.wikipedia.org/wiki/Stack_buffer_overflow Stack overflow] and abnormal program termination or crashing.
=Recursive Data types=
[https://en.wikipedia.org/wiki/Recursive_data_type Recursive data types] contain references (i. e. pointer in [[C]]) to objects of the same type to build [https://en.wikipedia.org/wiki/Directed_graph directed graphs], such as [[Linked List|linked lists]] or [[Search Tree|trees]].
=Recursive Algorithms=
==Searching==
Tree-like data structures which are traversed in [[Depth-first|depth-first]] manner can be implemented with recursion using a [[Stack|stack]] of nodes. [[Minimax]] and [[Alpha-Beta|alpha-beta]] are typical examples of indirect recursive routines, where Min calls Max and Max calls Min, and [[Negamax]] turns the indirect recursion to a direct one. While [https://en.wikipedia.org/wiki/Tail_recursion tail recursion] or [https://en.wikipedia.org/wiki/Primitive_recursive_function primitive recursion] can easily turned into iterative solutions, it is more complicated for not primitive recursion. However, recursion can turned to a non-recursive version based on the use of [https://en.wikipedia.org/wiki/Continuation continuations], see [[Iterative Search]].
[[Donald Knuth|Knuth]] and Moore already introduced an [[Knuth-iterative|iterative solution]] of [[Alpha-Beta]] in 1975 <ref>[[Donald Knuth]], [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore] ('''1975'''). ''[http://www.scribd.com/doc/28194932/An-Analysis-of-Alpha-Beta-Pruning An analysis of alpha-beta pruning].'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4</ref> :
It is interesting to convert this recursive procedure to an iterative (non-recursive) form by a sequence of mechanical transformations, and to apply simple optimizations which preserve program correctness. The resulting procedure is surprisingly simple, but not as easy to prove correct as the recursive form.
So called recursive [[Pruning|pruning]], especially [[Null Move Pruning|null move pruning]], or [[Extensions|extensions]] refers to the fact that these events may occur multiple times inside a variation or path of the (recursive) search process.
==Sorting==
A well-known [https://en.wikipedia.org/wiki/Sorting_algorithm sorting algorithm] is [https://en.wikipedia.org/wiki/Quicksort Quicksort] developed in 1960 by [[Mathematician#CARHoare|C. A. R. Hoare]]. It recursively partitions and sorts two sub-lists from a list, whose elements are either less and greater a chosen [https://en.wikipedia.org/wiki/Pivot_element pivot element]. However, for [[Move Ordering|move ordering]] to sort [[Move List|move lists]] in [[Alpha-Beta|alpha-beta]], most chess programmer use a [https://en.wikipedia.org/wiki/Selection_sort selection sort] to pick a [[Moves|move]] with best assigned score, since the effort to sort other moves may needless in case of a [[Beta-Cutoff|beta-cutoff]].
[[FILE:Sorting quicksort anim.gif|none|border|text-bottom]]
Visualization of the [https://en.wikipedia.org/wiki/Quicksort quicksort algorithm] <ref>[https://en.wikipedia.org/wiki/Quicksort Quicksort from Wikipedia]</ref>
=See also=
* [[ABDADA]]
: [[ABDADA#Recursion|Recursive vs. Iterative Search]]
* [[Alpha-Beta]]
* [[Backtracking]]
* [[De Bruijn Sequence Generator]]
* [[Depth-First]]
* [[Iteration]]
* [[Iterative Search]]
* [[Jamboree]]
* [[Minimax]]
* [[Negamax]]
* [[Cilk#ParallelAlphaBeta|Parallel Alpha-Beta]] in [[Cilk]]
=Publications=
* [[John McCarthy]] ('''1960'''). ''Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I'', [[Massachusetts Institute of Technology]], [http://www-formal.stanford.edu/jmc/recursive.pdf pdf]
* [http://www.mathnet.ru/php/person.phtml?option_lang=eng&personid=63222 V. I. Sobel'man], [[Mikhail R. Shura-Bura]] ('''1962'''). ''[http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=7886&option_lang=eng Realization of recursive procedures in the language of AlGOL-60]''. (Реализация Рекурсивных Процедур В Языке Алгол-60) [http://www.mathnet.ru/php/archive.phtml?jrnid=zvmmf&option_lang=eng&wshow=statlist Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki], Vol. 2, No. 2
* [[Michael Levin]] ('''1963'''). ''Primitive Recursion''. AIM-055, reprint available from [http://dspace.mit.edu/handle/1721.1/6109 DSpace] at [[Massachusetts Institute of Technology|MIT]]
* [http://www.finseth.com/parts/index.php Craig A. Finseth] ('''1980'''). ''[http://www.atariarchives.org/bcc3/showpage.php?page=45 Something is Missing (Implementing recursion and stacks in BASIC)]''. [[Creative Computing#Best3|The Best of Creative Computing Volume 3]] » [[Basic]]
* [[Ingo Althöfer]] ('''1988'''). ''On the Complexity of Searching Game Trees and Other Recursion Trees''. Journal of Algorithms, Vol. 9, No. 4
* [[Ingo Althöfer]] ('''1991''') ''On pathology in game tree and other recursion tree models''. Habilitation Thesis, [https://en.wikipedia.org/wiki/University_of_Bielefeld University of Bielefeld]
* [[Donald Knuth]] ('''1991'''). ''Textbook examples of recursion''. [https://arxiv.org/abs/cs/9301113 arXiv:cs/9301113]
* [[Raymond Smullyan]] ('''1993'''). ''Recursion Theory for Metamathematics''. [https://en.wikipedia.org/wiki/Oxford_University_Press Oxford University Press] <ref>[https://en.wikipedia.org/wiki/Metamathematics Metamathematics from Wikipedia]</ref>
* [[Richard J. Lorentz]] ('''1994'''). ''[http://www.abebooks.com/book-search/isbn/0893919136/ Recursive algorithms]''. Intellect Books
* [[Kevin Coplan]] ('''1998'''). ''Synthesis of Chess and Chess-like Endgames by Recursive Optimisation''. [[ICGA Journal#21_3|ICCA Journal, Vol. 21, No. 3]]
* [[David Slate]], [[Peter W. Frey]] ('''2009'''). ''Recursive Binary Partitioning, Old Dogs with New Tricks'', [http://www.sigkdd.org/kdd2009/index.html KDD Conference 2009], slides as [http://clopinet.com/isabelle/Projects/KDDcup09/Slides/Frey_slides.pdf pdf] <ref>[http://www.kddcup-orange.com/winners.php Results of the KDD cup 2009]</ref>
=Forum Posts=
* [http://hr.userweb.mwn.de/tmp/nat-cf.html Was ist rekursiv? irrelevant!] by [[Helmut Richter]], [http://groups.google.com/group/sci.lang/topics sci.lang], September 29, 1998
* [http://www.talkchess.com/forum/viewtopic.php?t=42588 how to print tree non-recursively] by [[Daniel Shawul]], [[CCC]], February 24, 2012 » [[Search Tree]], [[Iteration]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48752 Recursive DTS-like search algorithm] by [[Peter Österlund]], [[CCC]], July 24, 2013 » [[Texel]], [[Parallel Search]]
=External Links=
==Recursion ==
* [https://en.wikipedia.org/wiki/Recursion Recursion from Wikipedia]
* [http://mathworld.wolfram.com/Recursion.html Recursion] by [http://mathworld.wolfram.com/about/author.html Weisstein, Eric W.] from [http://mathworld.wolfram.com/ Wolfram MathWorld]
* [https://en.wikipedia.org/wiki/Recursion_%28computer_science%29 Recursion (computer science) from Wikipedia]
* [https://en.wikipedia.org/wiki/Recursive_acronym Recursive acronym from Wikipedia]
* [https://en.wikipedia.org/wiki/Recursive_data_type Recursive data type from Wikipedia]
* [https://en.wikipedia.org/wiki/Recursive_definition Recursive definition from Wikipedia]
* [http://www.mi.sanu.ac.rs/vismath/bridges2005/burns/index.html Recursion in Nature, Mathematics and Art] by [[Mathematician#AMBurns|Anne M. Burns]]
* [https://en.wikipedia.org/wiki/Recursion_theory Recursion theory from Wikipedia]
==Recursive Functions==
* [https://en.wikipedia.org/wiki/Recursive_function Recursive function from Wikipedia]
: [https://en.wikipedia.org/wiki/Primitive_recursive_function Primitive recursive function from Wikipedia]
: [https://en.wikipedia.org/wiki/Leaf_subroutine Leaf subroutine from Wikipedia]
: [https://en.wikipedia.org/wiki/Tail_call Tail call from Wikipedia]
===Ackermann Function===
* [https://en.wikipedia.org/wiki/Ackermann_function Ackermann function from Wikipedia] » [[Mathematician#WAckermann|Wilhelm Ackermann]]
* [http://mathworld.wolfram.com/AckermannFunction.html Ackermann Function] by [http://mathworld.wolfram.com/about/author.html Weisstein, Eric W.] from [http://mathworld.wolfram.com/ Wolfram MathWorld]
===McCarthy 91-Function===
Introduced by [[Mathematician#Manna|Zohar Manna]], [[Mathematician#APnueli|Amir Pnueli]] and [[John McCarthy]] in 1970.
* [https://en.wikipedia.org/wiki/McCarthy_91_function McCarthy 91 function from Wikipedia]
* [http://mathworld.wolfram.com/McCarthy91-Function.html McCarthy 91-Function] by [http://mathworld.wolfram.com/about/author.html Weisstein, Eric W.] from [http://mathworld.wolfram.com/ Wolfram MathWorld]
===Tak ===
* [https://en.wikipedia.org/wiki/Tak_(function) Tak (function) from Wikipedia]
* [http://mathworld.wolfram.com/TAKFunction.html TAK Function] by [http://mathworld.wolfram.com/about/author.html Weisstein, Eric W.] from [http://mathworld.wolfram.com/ Wolfram MathWorld]
==Self-reference==
* [https://en.wikipedia.org/wiki/Self-reference Self-reference from Wikipedia]
* [https://en.wikipedia.org/wiki/Droste_effect Droste effect from Wikipedia]
: [[FILE:Droste cacao 100gr blikje, foto 02.JPG|none|border|text-bottom|300px]]
: [http://escherdroste.math.leidenuniv.nl/ Escher and the Droste effect] - [[Leiden University|Universiteit Leiden]] » [[Arts#Escher|M. C. Escher]]
* [https://en.wikipedia.org/wiki/Mise_en_abyme Mise en abyme from Wikipedia]
* [https://en.wikipedia.org/wiki/Ouroboros Ouroboros from Wikipedia]
: [[FILE:Serpiente alquimica.jpg|none|border|text-bottom|300px]]
* [https://en.wikipedia.org/wiki/The_Treachery_of_Images The Treachery of Images] by [[Arts#Magritte|René Magritte]]
: [[FILE:MagrittePipe.jpg|none|border|text-bottom|link=https://en.wikipedia.org/wiki/The_Treachery_of_Images|300px]]
==Fractals==
* [https://en.wikipedia.org/wiki/Fractal Fractal from Wikipedia]
: [https://en.wikipedia.org/wiki/Hilbert_curve Hilbert curve from Wikipedia] » [[Mathematician#Hilbert|David Hilbert]]
: [https://en.wikipedia.org/wiki/Koch_snowflake Koch snowflake from Wikipedia] » [[Mathematician#HvKoch|Helge von Koch]]
: [[FILE:Von Koch curve.gif|none|border|text-bottom|300px]]
: [https://en.wikipedia.org/wiki/Peano_curve Peano curve from Wikipedia] » [[Mathematician#Peano|Giuseppe Peano]]
: [https://en.wikipedia.org/wiki/Sierpinski_triangle Sierpinski triangle from Wikipedia] » [[Mathematician#Sierpinski|Wacław Sierpiński]]
==Misc==
* [https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm Divide and conquer algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Eternal_return Eternal return from Wikipedia]
* [https://en.wikipedia.org/wiki/Lambda_calculus Lambda Calculus from Wikipedia]
* [https://en.wikipedia.org/wiki/Knights_of_the_Lambda_Calculus Knights of the Lambda Calculus from Wikipedia] » [[Mathematician#Church|Alonzo Church]]
* [https://en.wikipedia.org/wiki/Mathematical_induction Mathematical induction from Wikipedia]
* [https://en.wikipedia.org/wiki/Recurrence_relations Recurrence relation from Wikipedia]
* [https://en.wikipedia.org/wiki/Reentrant_%28subroutine%29 Reentrant (subroutine) from Wikipedia]
* [https://en.wikipedia.org/wiki/Turing_completeness Turing completeness from Wikipedia]
* [[Videos#ReturntoForever|Return to Forever]] - [https://en.wikipedia.org/wiki/Musikladen Musikladen Extra], 1974, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[Videos#ChickCorea|Chick Corea]], [https://en.wikipedia.org/wiki/Bill_Connors Bill Connors], [[Videos#StanleyClarke|Stanley Clarke]], [https://en.wikipedia.org/wiki/Lenny_White Lenny White]
: {{#evu:https://www.youtube.com/watch?v=ppUpj90YAFU|alignment=left|valignment=top}}
* [[Videos#ReturntoForever|Return to Forever]] - [https://en.wikipedia.org/wiki/Hymn_of_the_Seventh_Galaxy Hymn of the Seventh Galaxy], [https://en.wikipedia.org/wiki/Montreux_Jazz_Festival Montreux Jazz Festival], 2008, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[Videos#ChickCorea|Chick Corea]], [[Videos#AlDiMeola|Al Di Meola]], [[Videos#StanleyClarke|Stanley Clarke]], [https://en.wikipedia.org/wiki/Lenny_White Lenny White]
: {{#evu:https://www.youtube.com/watch?v=d0LJ2GlziJk|alignment=left|valignment=top}}
=References=
<references />
'''[[Algorithms|Up one Level]]'''
[[FILE:Bottrop_Halde_Beckstraße_Tetraeder.JPG|border|right|thumb|[https://en.wikipedia.org/wiki/Tetrahedron_in_Bottrop Tetrahedron in Bottrop] <ref>[https://en.wikipedia.org/wiki/Tetrahedron Tetrahedron] in [https://en.wikipedia.org/wiki/Bottrop Bottrop], [https://en.wikipedia.org/wiki/North_Rhine-Westphalia North Rhine-Westphalia], Germany, part of [[Arts#IndustrialHeritageTrail|The Industrial Heritage Trail]], [https://commons.wikimedia.org/wiki/File:Bottrop_-_Halde_Beckstra%C3%9Fe_-_Tetraeder_03_ies.jpg Image] by [[Gerd Isenberg]], April 08, 2017. The design is reminiscent of the [https://en.wikipedia.org/wiki/Sierpinski_triangle#Analogues_in_higher_dimensions Sierpinski tetrix] : placing four half-size tetrahedra corner to corner and adding an octahedron in the middle, a full-size tetrahedron is formed; this process can be repeated recursively to form larger and larger tetrahedra, from [https://en.wikipedia.org/wiki/Tetrahedron_in_Bottrop Tetrahedron in Bottrop from Wikipedia], [https://commons.wikimedia.org/wiki/Category:Tetraeder_Bottrop Category:Tetraeder Bottrop] - [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [http://www.halden.ruhr/halden.html Halden im Ruhrgebiet] (German)</ref> ]]
'''Recursion''' is a technique to define a function, or process of repeating objects, in a [https://en.wikipedia.org/wiki/Self-similarity self-similar] way. In computer science it is a method or algorithm where the solution to a problem depends on solutions to smaller instances of the same problem.
=Sample=
In the [https://en.wikipedia.org/wiki/Tower_of_Hanoi Tower of Hanoi] puzzle to move N disks from peg A to C can be reduced to three sub problems:
# Moving N-1 disks from peg A to intermediate peg B
# Move the largest Disk N from peg A to target C
# Finally move the N-1 parked disks from B to C
: [[FILE:Tower of Hanoi.gif|none|border|text-bottom|link=https://de.wikipedia.org/wiki/T%C3%BCrme_von_Hanoi]]
=Recursive Definitions=
A [https://en.wikipedia.org/wiki/Recursive_definition recursive definition] of an object refers inductive terms of itself. A function set need to specify the function for some discrete values like zero, one or empty (base case), and to reduce all other cases by [https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm divide and conquer] toward the base case. [https://en.wikipedia.org/wiki/Recurrence_relations Recurrence relation] is an equation that recursively defines a sequence of symbols or numbers <ref>[https://en.wikipedia.org/wiki/Hofstadter_sequence Hofstadter sequence from Wikipedia]</ref>.
''Some more or less computer chess related examples ...''
==PGN Syntax==
The [https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form BNF]-like [https://en.wikipedia.org/wiki/Syntax Syntax] of the [[Portable Game Notation]] by [[Steven Edwards]] contains some recursive definitions, most [https://en.wikipedia.org/wiki/Tail_recursion tail recursion] for iteration of games, and tag-pairs and elements inside a game <ref>[http://www.thechessdrum.net/PGN_Reference.txt Standard: Portable Game Notation Specification and Implementation Guide] by [[Steven Edwards]], 18: Formal syntax</ref> :
<pre>
<PGN-database> ::= <PGN-game> <PGN-database>
<empty>
<tag-section> ::= <tag-pair> <tag-section>
<empty>
<element-sequence> ::= <element> <element-sequence>
<recursive-variation> <element-sequence>
<empty>
<recursive-variation> ::= ( <element-sequence> )
</pre>
==Index of PV-Array==
An index of a [[Triangular PV-Table]] may be defined recursively that way ...
index(0) = 0
index(ply+1) = index(ply) + N - ply
...which can be trivially transformed from [https://en.wikipedia.org/wiki/Tail_recursion tail recursion] to [https://en.wikipedia.org/wiki/Iteration iteration], finally applying a [https://en.wikipedia.org/wiki/Summation summation]:
index(ply) = ½ ply (2N + 1 - ply )
==Population Count==
The recursive definition of [[Population Count|population count]] (number of one-bits in a computer word i. e. a [[Bitboards|bitboard]]) can be transformed to iteration as well, but lacks an arithmetical sum-formula:
popcnt(0) = 0
popcnt(n) = popcnt(n ÷ 2) + (n mod 2)
<span id="InfixExpression"></span>
==Infix Expression==
[https://en.wikipedia.org/wiki/Syntax_%28programming_languages%29 Formal syntax] of [[Languages|
programming languages]] likely contain recursive definitions, i. e. [https://en.wikipedia.org/wiki/Parsing parsing] of arithmetical (and/or boolean) [https://en.wikipedia.org/wiki/Infix_notation infix notation] therefor implies indirect recursion, as demonstrated in following example with constants and [https://en.wikipedia.org/wiki/Elementary_arithmetic elementary arithmetic] only, which might even evaluated at [https://en.wikipedia.org/wiki/Compile_time compile time]:
''[https://en.wikipedia.org/wiki/Terminal_and_nonterminal_symbols Terminal and none terminal symbols] of a variant of [https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form BNF] below are embedded in ' ' resp. < >.''
<pre>
<expression> ::= <term> [ {'+' | '-'} <term> ]...
<term> ::= <factor> [ {'*' | '/'} <factor> ]...
<factor> ::= <constant> | '(' <expression> ')'
</pre>
=Implementation=
In [https://en.wikipedia.org/wiki/Procedural_programming procedual programming], recursion is done by a procedure aka [https://en.wikipedia.org/wiki/Subroutine subroutine], method or function, which calls itself if no base case is determined, utilizing the [[Stack|processor stack]]. One has to take care the nesting is not too deep or infinite, which yields in a [https://en.wikipedia.org/wiki/Stack_buffer_overflow Stack overflow] and abnormal program termination or crashing.
=Recursive Data types=
[https://en.wikipedia.org/wiki/Recursive_data_type Recursive data types] contain references (i. e. pointer in [[C]]) to objects of the same type to build [https://en.wikipedia.org/wiki/Directed_graph directed graphs], such as [[Linked List|linked lists]] or [[Search Tree|trees]].
=Recursive Algorithms=
==Searching==
Tree-like data structures which are traversed in [[Depth-first|depth-first]] manner can be implemented with recursion using a [[Stack|stack]] of nodes. [[Minimax]] and [[Alpha-Beta|alpha-beta]] are typical examples of indirect recursive routines, where Min calls Max and Max calls Min, and [[Negamax]] turns the indirect recursion to a direct one. While [https://en.wikipedia.org/wiki/Tail_recursion tail recursion] or [https://en.wikipedia.org/wiki/Primitive_recursive_function primitive recursion] can easily turned into iterative solutions, it is more complicated for not primitive recursion. However, recursion can turned to a non-recursive version based on the use of [https://en.wikipedia.org/wiki/Continuation continuations], see [[Iterative Search]].
[[Donald Knuth|Knuth]] and Moore already introduced an [[Knuth-iterative|iterative solution]] of [[Alpha-Beta]] in 1975 <ref>[[Donald Knuth]], [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore] ('''1975'''). ''[http://www.scribd.com/doc/28194932/An-Analysis-of-Alpha-Beta-Pruning An analysis of alpha-beta pruning].'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4</ref> :
It is interesting to convert this recursive procedure to an iterative (non-recursive) form by a sequence of mechanical transformations, and to apply simple optimizations which preserve program correctness. The resulting procedure is surprisingly simple, but not as easy to prove correct as the recursive form.
So called recursive [[Pruning|pruning]], especially [[Null Move Pruning|null move pruning]], or [[Extensions|extensions]] refers to the fact that these events may occur multiple times inside a variation or path of the (recursive) search process.
==Sorting==
A well-known [https://en.wikipedia.org/wiki/Sorting_algorithm sorting algorithm] is [https://en.wikipedia.org/wiki/Quicksort Quicksort] developed in 1960 by [[Mathematician#CARHoare|C. A. R. Hoare]]. It recursively partitions and sorts two sub-lists from a list, whose elements are either less and greater a chosen [https://en.wikipedia.org/wiki/Pivot_element pivot element]. However, for [[Move Ordering|move ordering]] to sort [[Move List|move lists]] in [[Alpha-Beta|alpha-beta]], most chess programmer use a [https://en.wikipedia.org/wiki/Selection_sort selection sort] to pick a [[Moves|move]] with best assigned score, since the effort to sort other moves may needless in case of a [[Beta-Cutoff|beta-cutoff]].
[[FILE:Sorting quicksort anim.gif|none|border|text-bottom]]
Visualization of the [https://en.wikipedia.org/wiki/Quicksort quicksort algorithm] <ref>[https://en.wikipedia.org/wiki/Quicksort Quicksort from Wikipedia]</ref>
=See also=
* [[ABDADA]]
: [[ABDADA#Recursion|Recursive vs. Iterative Search]]
* [[Alpha-Beta]]
* [[Backtracking]]
* [[De Bruijn Sequence Generator]]
* [[Depth-First]]
* [[Iteration]]
* [[Iterative Search]]
* [[Jamboree]]
* [[Minimax]]
* [[Negamax]]
* [[Cilk#ParallelAlphaBeta|Parallel Alpha-Beta]] in [[Cilk]]
=Publications=
* [[John McCarthy]] ('''1960'''). ''Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I'', [[Massachusetts Institute of Technology]], [http://www-formal.stanford.edu/jmc/recursive.pdf pdf]
* [http://www.mathnet.ru/php/person.phtml?option_lang=eng&personid=63222 V. I. Sobel'man], [[Mikhail R. Shura-Bura]] ('''1962'''). ''[http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=7886&option_lang=eng Realization of recursive procedures in the language of AlGOL-60]''. (Реализация Рекурсивных Процедур В Языке Алгол-60) [http://www.mathnet.ru/php/archive.phtml?jrnid=zvmmf&option_lang=eng&wshow=statlist Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki], Vol. 2, No. 2
* [[Michael Levin]] ('''1963'''). ''Primitive Recursion''. AIM-055, reprint available from [http://dspace.mit.edu/handle/1721.1/6109 DSpace] at [[Massachusetts Institute of Technology|MIT]]
* [http://www.finseth.com/parts/index.php Craig A. Finseth] ('''1980'''). ''[http://www.atariarchives.org/bcc3/showpage.php?page=45 Something is Missing (Implementing recursion and stacks in BASIC)]''. [[Creative Computing#Best3|The Best of Creative Computing Volume 3]] » [[Basic]]
* [[Ingo Althöfer]] ('''1988'''). ''On the Complexity of Searching Game Trees and Other Recursion Trees''. Journal of Algorithms, Vol. 9, No. 4
* [[Ingo Althöfer]] ('''1991''') ''On pathology in game tree and other recursion tree models''. Habilitation Thesis, [https://en.wikipedia.org/wiki/University_of_Bielefeld University of Bielefeld]
* [[Donald Knuth]] ('''1991'''). ''Textbook examples of recursion''. [https://arxiv.org/abs/cs/9301113 arXiv:cs/9301113]
* [[Raymond Smullyan]] ('''1993'''). ''Recursion Theory for Metamathematics''. [https://en.wikipedia.org/wiki/Oxford_University_Press Oxford University Press] <ref>[https://en.wikipedia.org/wiki/Metamathematics Metamathematics from Wikipedia]</ref>
* [[Richard J. Lorentz]] ('''1994'''). ''[http://www.abebooks.com/book-search/isbn/0893919136/ Recursive algorithms]''. Intellect Books
* [[Kevin Coplan]] ('''1998'''). ''Synthesis of Chess and Chess-like Endgames by Recursive Optimisation''. [[ICGA Journal#21_3|ICCA Journal, Vol. 21, No. 3]]
* [[David Slate]], [[Peter W. Frey]] ('''2009'''). ''Recursive Binary Partitioning, Old Dogs with New Tricks'', [http://www.sigkdd.org/kdd2009/index.html KDD Conference 2009], slides as [http://clopinet.com/isabelle/Projects/KDDcup09/Slides/Frey_slides.pdf pdf] <ref>[http://www.kddcup-orange.com/winners.php Results of the KDD cup 2009]</ref>
=Forum Posts=
* [http://hr.userweb.mwn.de/tmp/nat-cf.html Was ist rekursiv? irrelevant!] by [[Helmut Richter]], [http://groups.google.com/group/sci.lang/topics sci.lang], September 29, 1998
* [http://www.talkchess.com/forum/viewtopic.php?t=42588 how to print tree non-recursively] by [[Daniel Shawul]], [[CCC]], February 24, 2012 » [[Search Tree]], [[Iteration]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48752 Recursive DTS-like search algorithm] by [[Peter Österlund]], [[CCC]], July 24, 2013 » [[Texel]], [[Parallel Search]]
=External Links=
==Recursion ==
* [https://en.wikipedia.org/wiki/Recursion Recursion from Wikipedia]
* [http://mathworld.wolfram.com/Recursion.html Recursion] by [http://mathworld.wolfram.com/about/author.html Weisstein, Eric W.] from [http://mathworld.wolfram.com/ Wolfram MathWorld]
* [https://en.wikipedia.org/wiki/Recursion_%28computer_science%29 Recursion (computer science) from Wikipedia]
* [https://en.wikipedia.org/wiki/Recursive_acronym Recursive acronym from Wikipedia]
* [https://en.wikipedia.org/wiki/Recursive_data_type Recursive data type from Wikipedia]
* [https://en.wikipedia.org/wiki/Recursive_definition Recursive definition from Wikipedia]
* [http://www.mi.sanu.ac.rs/vismath/bridges2005/burns/index.html Recursion in Nature, Mathematics and Art] by [[Mathematician#AMBurns|Anne M. Burns]]
* [https://en.wikipedia.org/wiki/Recursion_theory Recursion theory from Wikipedia]
==Recursive Functions==
* [https://en.wikipedia.org/wiki/Recursive_function Recursive function from Wikipedia]
: [https://en.wikipedia.org/wiki/Primitive_recursive_function Primitive recursive function from Wikipedia]
: [https://en.wikipedia.org/wiki/Leaf_subroutine Leaf subroutine from Wikipedia]
: [https://en.wikipedia.org/wiki/Tail_call Tail call from Wikipedia]
===Ackermann Function===
* [https://en.wikipedia.org/wiki/Ackermann_function Ackermann function from Wikipedia] » [[Mathematician#WAckermann|Wilhelm Ackermann]]
* [http://mathworld.wolfram.com/AckermannFunction.html Ackermann Function] by [http://mathworld.wolfram.com/about/author.html Weisstein, Eric W.] from [http://mathworld.wolfram.com/ Wolfram MathWorld]
===McCarthy 91-Function===
Introduced by [[Mathematician#Manna|Zohar Manna]], [[Mathematician#APnueli|Amir Pnueli]] and [[John McCarthy]] in 1970.
* [https://en.wikipedia.org/wiki/McCarthy_91_function McCarthy 91 function from Wikipedia]
* [http://mathworld.wolfram.com/McCarthy91-Function.html McCarthy 91-Function] by [http://mathworld.wolfram.com/about/author.html Weisstein, Eric W.] from [http://mathworld.wolfram.com/ Wolfram MathWorld]
===Tak ===
* [https://en.wikipedia.org/wiki/Tak_(function) Tak (function) from Wikipedia]
* [http://mathworld.wolfram.com/TAKFunction.html TAK Function] by [http://mathworld.wolfram.com/about/author.html Weisstein, Eric W.] from [http://mathworld.wolfram.com/ Wolfram MathWorld]
==Self-reference==
* [https://en.wikipedia.org/wiki/Self-reference Self-reference from Wikipedia]
* [https://en.wikipedia.org/wiki/Droste_effect Droste effect from Wikipedia]
: [[FILE:Droste cacao 100gr blikje, foto 02.JPG|none|border|text-bottom|300px]]
: [http://escherdroste.math.leidenuniv.nl/ Escher and the Droste effect] - [[Leiden University|Universiteit Leiden]] » [[Arts#Escher|M. C. Escher]]
* [https://en.wikipedia.org/wiki/Mise_en_abyme Mise en abyme from Wikipedia]
* [https://en.wikipedia.org/wiki/Ouroboros Ouroboros from Wikipedia]
: [[FILE:Serpiente alquimica.jpg|none|border|text-bottom|300px]]
* [https://en.wikipedia.org/wiki/The_Treachery_of_Images The Treachery of Images] by [[Arts#Magritte|René Magritte]]
: [[FILE:MagrittePipe.jpg|none|border|text-bottom|link=https://en.wikipedia.org/wiki/The_Treachery_of_Images|300px]]
==Fractals==
* [https://en.wikipedia.org/wiki/Fractal Fractal from Wikipedia]
: [https://en.wikipedia.org/wiki/Hilbert_curve Hilbert curve from Wikipedia] » [[Mathematician#Hilbert|David Hilbert]]
: [https://en.wikipedia.org/wiki/Koch_snowflake Koch snowflake from Wikipedia] » [[Mathematician#HvKoch|Helge von Koch]]
: [[FILE:Von Koch curve.gif|none|border|text-bottom|300px]]
: [https://en.wikipedia.org/wiki/Peano_curve Peano curve from Wikipedia] » [[Mathematician#Peano|Giuseppe Peano]]
: [https://en.wikipedia.org/wiki/Sierpinski_triangle Sierpinski triangle from Wikipedia] » [[Mathematician#Sierpinski|Wacław Sierpiński]]
==Misc==
* [https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm Divide and conquer algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Eternal_return Eternal return from Wikipedia]
* [https://en.wikipedia.org/wiki/Lambda_calculus Lambda Calculus from Wikipedia]
* [https://en.wikipedia.org/wiki/Knights_of_the_Lambda_Calculus Knights of the Lambda Calculus from Wikipedia] » [[Mathematician#Church|Alonzo Church]]
* [https://en.wikipedia.org/wiki/Mathematical_induction Mathematical induction from Wikipedia]
* [https://en.wikipedia.org/wiki/Recurrence_relations Recurrence relation from Wikipedia]
* [https://en.wikipedia.org/wiki/Reentrant_%28subroutine%29 Reentrant (subroutine) from Wikipedia]
* [https://en.wikipedia.org/wiki/Turing_completeness Turing completeness from Wikipedia]
* [[Videos#ReturntoForever|Return to Forever]] - [https://en.wikipedia.org/wiki/Musikladen Musikladen Extra], 1974, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[Videos#ChickCorea|Chick Corea]], [https://en.wikipedia.org/wiki/Bill_Connors Bill Connors], [[Videos#StanleyClarke|Stanley Clarke]], [https://en.wikipedia.org/wiki/Lenny_White Lenny White]
: {{#evu:https://www.youtube.com/watch?v=ppUpj90YAFU|alignment=left|valignment=top}}
* [[Videos#ReturntoForever|Return to Forever]] - [https://en.wikipedia.org/wiki/Hymn_of_the_Seventh_Galaxy Hymn of the Seventh Galaxy], [https://en.wikipedia.org/wiki/Montreux_Jazz_Festival Montreux Jazz Festival], 2008, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[Videos#ChickCorea|Chick Corea]], [[Videos#AlDiMeola|Al Di Meola]], [[Videos#StanleyClarke|Stanley Clarke]], [https://en.wikipedia.org/wiki/Lenny_White Lenny White]
: {{#evu:https://www.youtube.com/watch?v=d0LJ2GlziJk|alignment=left|valignment=top}}
=References=
<references />
'''[[Algorithms|Up one Level]]'''
