Recursive Functions

Any function written using an iterative code can be converted into a recursive code. This does not guarantee that the resulting program will be easy to understand but often, the program results in a compact and readable code.

Recursive functions are often simple and elegant, and their correctness can be easily verified.

Many mathematical functions are defined recursively, and their translation into a programming language is often easy.

If used carelessly, recursion can sometimes result in an inefficient function.

Algorithms that are by nature recursive, such as the factorial, Fibonacci, or power, can be implemented as either iterative or recursive code. However, recursive functions are generally smaller and more efficient than their looping equivalents.

Recursion is also useful when the data structure that the algorithm is to operate on is recursively defined. Examples of such data structures are linked lists and trees.

Recursion is valuable is when we use ‘divide and conquer’ and ‘backtracking’ as algorithm design paradigms.

Writing Recursive Code

The general approach to writing a recursive function is

1. Write the function header  to make sure what the function will do and how it will be called.

2. Decompose the problem into sub-problems. Identify clearly the non-recursive case of the problem (end case or base case).

3. Write recursive calls to solve those sub-problems whose form is similar to that of the original problem.

4. Write the code to combine, enhance, or modify the results of the recursive call(s).

5. Write the end condition(s) to handle any situations that are not handled properly by the recursive portion of the program.

Correctness of recursion

The following five conditions must hold true for recursion to work.

1. A recursive function must have at least one end condition and one recursive case.

2. The test for the end condition has to execute prior to the recursive call.

3. The problem must be broken down in such a way that the recursive call is closer to the base case. The base case is reached in a finite number of recursive calls.

4. The recursive call must not skip over the base case.

5. Verify that the non-recursive code of the function is operating correctly.