### Table of Contents

In computer science, **Recursion** is a situation where a function calls itself within the function body. The motivation for this is to constantly break a problem down into continuously smaller pieces, until a known solution to a piece is reached. Once a piece of the problem is so small that it is trivial to solve without the use of more recursion, the function can then use the trivial solutions to construct a complete solution for the original problem.

Along with pointers and backtracking, recursion is generally one of the most difficult concepts for beginning computer scientists to understand. Unlike pointers - where the theory is relatively simple and the implementation is challenging - recursion is simple to implement yet it is difficult to fully comprehend all the effects of using it. (1)

## Requirements for a Recursive Function

### One or more base cases

Each *base case* is a trivial solution to the overall problem (as mentioned above). Again, these are the cases where more recursion is not needed to return a solution.

Typically, these cases have very simple return statements - often with just one variable or constant value - because they handle very trivial situations.

### One or more recursive cases

Each *recursive case* is a situation where a trivial solution still cannot be achieved, so the function uses more recursion in order to achieve a solution. A function must call itself with at least one argument changing in value in order to

### Inputs that have mutable values

A recursive function reaches the base case(s) by calling itself with modified values. In general, this tends to be an increase or decrease by some number until a base case dependent on this number is reached. Thus, by definition, the inputs to a recursive function must be modifiable in value in order to achieve a base case. Otherwise, the function will never return and will remain suspended in an endless loop.

## The Dangers of Using Recursion

### Infinite Recursion

As mentioned above, at least one base case much be reached by the function in order for the function to return. Should no base case(s) be reached, the function will never return. A programmer must take care that these cases can be reached!

### Performance

Recursive functions tend to have a high big-o complexity and require large amounts of system resources when compared to iterative algorithms (such as sorting). It is not uncommon to see polynomial - O(n^2) - or even factorial - O(n!) - complexity for recursive functions. Furthermore, function calls tend to use stack memory in most higher-level programming language, which is relatively limited. Since recursive functions repeatedly call themselves, they use stack space at an alarming rate and are generally not scale-able.

### Thinking Recursively instead of Iteratively

In extremely general terms, it is generally more acceptable to use iteration instead of recursion. There are two major reasons for this:

- Iteration is typically more efficient than recursion in most high-level programming languages, making it execute faster.
- The syntax for iteration is generally simpler than that of recursion (and requires one less function call), making it easier to code.

Using recursion where iteration is more appropriate is, then, counter-productive and should be avoided. When in doubt as to which is more appropriate for a situation, the general rule of thumb is to “use iteration if you can”.

## Examples

All examples are coded in C++.

### Factorial Calculation

The computation of factorial numbers, such as 5!, is relatively straightforward to do with a recursive function. This is because for any arbitrary number N, N! = N * (N-1) * (N-2)…

- 2 * 1. Our base case then must be where N = 1, since it is final “ending point” for all factorial calculations.

The following code has been taken from this site, which also contains a more in-depth discussion of recursive functions.

int myFactorial( int integer) { if( integer == 1) return 1; else { return (integer * (myFactorial(integer-1))); } }

### Towers of Hanoi

The famous (or perhaps infamous) Towers of Hanoi puzzle is a classic example of recursion in action. In the puzzle, a specified number of disks of varying sizes must be moved between 3 pegs. Once all disks are on the same peg in size order (with largest on the bottom and smallest on the top), the puzzle is considered “complete”.

One approach to solve this problem can be found on this site and the recursive function is as follows:

void hanoi(int n, string source, string destination, string help) { if (n == 1) { cout << "Move 1 disk from " << source << " to " << destination << endl; } else { hanoi(n - 1, source, help, destination);

The above function's complexity is exponential, specifically O(2^n - 1). One peg is the initial destination of all the disks (“source”), one is used as the final destination for all the disks in the appropriate order (“destination”), and the final peg is used as a helper to achieve this goal (“help”). The base case is when only 1 disk is on a peg, as it is trivial to transfer it to the destination.