# Recursion

Recursion is a difficult topic for most beginners, so some of you may choose to follow the link to First Textbook Examples and learn by running programs before reading the theory below.

Recursion takes place when a procedure or function calls itself. The calling instance of the subroutine must be able to resume from where it left off when the subroutine it called has completed. Its return address and values of local variables must be stored. An activation record, used for this purpose, is pushed onto the stack for each recursive call. There must be a stopping condition within the recursive subroutine to limit the number of recursive calls and hence prevent stack overflow.

A novice can find most recursive code difficult to follow, so the first examples in textbooks and tutorials are relatively easy to understand. Unfortunately, these simple examples may not be not particularly useful because the iterative solutions to the same problems are efficient and very easy to understand. Our first section describes the relatively straightforward factorial and Fibonacci programs.

Recursion provides neat, elegant solutions to certain problems such as the processing of tree data structures. These problems can be more difficult to code by the alternative, iterative, method, which may require the programmer to maintain a stack within the program. Although this stack would occupy less memory than the stack of activation records in a recursive solution, this advantage is unlikely to outweigh the elegance and convenience of recursion. We provide several recursive functions in our section on binary search trees.

You may wish to look at our Graphics tutorial before studying the Fractal section, which covers the Sierpinski carpet and the Sierpinski curve. Recursive solutions are often ideally suited to the generation of fractals because of their self-similarity. Recursion may be indirect, such as when procedure A calls procedure B which then calls A. Program SierpinskiCurve gives examples of such mutual recursion.