Recursion is a technique to define a function, or process of repeating objects, in a 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, i. e. in Tower of Hanoi puzzle to move N disks from peg A to C can be reduced to three sub problems, first by moving N-1 disks from peg A to intermediate peg B, second to move the largest Disk N from peg A to target C, to finally move the N-1 parked disks from B to C.

A 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 divide and conquer toward the base case. Recurrence relation is an equation that recursively defines a sequence of symbols or numbers ^{[2]}.

Some more or less computer chess related examples ...

The recursive definition of population count (number of one-bits in a computer word i. e. a bitboard) can be transformed to iteration as well, but lacks an arithmetical sum-formula:

In procedual programming, recursion is done by a procedure aka subroutine, method or function, which calls itself if no base case is determined, utilizing the processor stack. One has to take care the nesting is not too deep or infinite, which yields in a Stack overflow and abnormal program termination or crashing.

Tree-like data structures which are traversed in depth-first manner can be implemented with recursion using a stack of nodes. Minimax and 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 tail recursion or 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 continuations, see Iterative Search.

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, especially null move pruning, or extensions refers to the fact that these events may occur multiple times inside a variation or path of the (recursive) search process.

Home * Programming * Algorithms * RecursionRecursionis a technique to define a function, or process of repeating objects, in a 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, i. e. in Tower of Hanoi puzzle to move N disks from peg A to C can be reduced to three sub problems, first by moving N-1 disks from peg A to intermediate peg B, second to move the largest Disk N from peg A to target C, to finally move the N-1 parked disks from B to C.^{[1]}## Table of Contents

## Recursive Definitions

A 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 divide and conquer toward the base case. Recurrence relation is an equation that recursively defines a sequence of symbols or numbers^{[2]}.Some more or less computer chess related examples ...## PGN Syntax

The BNF-like Syntax of the Portable Game Notation by Steven Edwards contains some recursive definitions, most tail recursion for iteration of games, and tag-pairs and elements inside a game^{[3]}:## Index of PV-Array

An index of a Triangular PV-Table may be defined recursively that way ......which can be trivially transformed from tail recursion to iteration, finally applying a summation:

## Population Count

The recursive definition of population count (number of one-bits in a computer word i. e. a bitboard) can be transformed to iteration as well, but lacks an arithmetical sum-formula:## Infix Expression

Formal syntax of programming languages likely contain recursive definitions, i. e. parsing of arithmetical (and/or boolean) infix notation therefor implies indirect recursion, as demonstrated in following example with constants and elementary arithmetic only, which might even evaluated at compile time:Terminal and none terminal symbols of a variant of BNF below are embedded in ' ' resp. < >.## Implementation

In procedual programming, recursion is done by a procedure aka subroutine, method or function, which calls itself if no base case is determined, utilizing the processor stack. One has to take care the nesting is not too deep or infinite, which yields in a Stack overflow and abnormal program termination or crashing.## Recursive Data types

Recursive data types contain references (i. e. pointer in C) to objects of the same type to build directed graphs, such as linked lists or trees.## Recursive Algorithms

## Searching

Tree-like data structures which are traversed in depth-first manner can be implemented with recursion using a stack of nodes. Minimax and 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 tail recursion or 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 continuations, see Iterative Search.Knuth and Moore already introduced an iterative solution of Alpha-Beta in 1975

^{[4]}: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, especially null move pruning, or 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 sorting algorithm is Quicksort developed in 1960 by C. A. R. Hoare. It recursively partitions and sorts two sub-lists from a list, whose elements are either less and greater a chosen pivot element. However, for move ordering to sort move lists in alpha-beta, most chess programmer use a selection sort to pick a move with best assigned score, since the effort to sort other moves may needless in case of a beta-cutoff.^{[5]}## See also

Recursive vs. Iterative Search

## Publications

1960).Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, Massachusetts Institute of Technology, pdf1962).Realization of recursive procedures in the language of AlGOL-60. (Реализация Рекурсивных Процедур В Языке Алгол-60) Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, Vol. 2, No. 21963).Primitive Recursion. AIM-055, reprint available from DSpace at MIT1980).Something is Missing (Implementing recursion and stacks in BASIC). The Best of Creative Computing Volume 3 » Basic1988).On the Complexity of Searching Game Trees and Other Recursion Trees. Journal of Algorithms, Vol. 9, No. 41991)On pathology in game tree and other recursion tree models. Habilitation Thesis, University of Bielefeld1991).Textbook examples of recursion. arXiv:cs/93011131993).Recursion Theory for Metamathematics. Oxford University Press^{[6]}1994).Recursive algorithms. Intellect Books1998).Synthesis of Chess and Chess-like Endgames by Recursive Optimisation. ICCA Journal, Vol. 21, No. 32009).Recursive Binary Partitioning, Old Dogs with New Tricks, KDD Conference 2009, slides as pdf^{[7]}## Forum Posts

## External Links

## Recursion

## Recursive Functions

Primitive recursive function from Wikipedia

Leaf subroutine from Wikipedia

Tail call from Wikipedia

## Ackermann Function

## McCarthy 91-Function

Introduced by Zohar Manna, Amir Pnueli and John McCarthy in 1970.## Tak

## Self-reference

Escher and the Droste effect - Universiteit Leiden » M. C. Escher

## Fractals

Hilbert curve from Wikipedia » David Hilbert

Koch snowflake from Wikipedia » Helge von Koch

Peano curve from Wikipedia » Giuseppe Peano

Sierpinski triangle from Wikipedia » Wacław Sierpiński

## Misc

Chick Corea, Al Di Meola, Stanley Clarke, Lenny White

## References

1975).An analysis of alpha-beta pruning.Artificial Intelligence, 6:293–326## What links here?

Up one Level