5.7. Recursion

• Functions can call other functions.
• Functions can even call themselves. This is called recursion.
• If a function is called recursively, it is required that for some condition, which will eventually be true, that the function not call itself again, but return to its calling function.

5.7.1. Four Basic Rules of Recursion

1. Base cases: You must always have some base or trivial case, which can be solved without recursion.
2. Making progress: For the cases that are to be solved recursively, the recursive call must always be to a case that makes progress toward the base case.
3. Design rule: Assume that all the recursive calls work. Use proof by induction.
4. Compound Interest Rule: [1] Never duplicate work by solving the same instance of a problem in separate recursive calls. If possible, use dynamic programming.

5.7.2. Recursion Examples

5.7.2.1. Simple mathematical recursion

Here is a recursive function to calculate the factorial value of a number.

#include <assert.h>

int fact( int n )
{
   assert( n >= 0 );
   if( n <= 1 )
      return 1;
   else
      return( n * fact(n - 1));
}

5.7.2.2. Towers of Hanoi

5.7.2.3. Printed triangle

Write a C program that uses a recursive function to print a triangle pattern similar to Homework 7 - Using a Static Local Variable. The function will take two integer arguments, the first argument tells it how many asterisk characters (*) and a space characters that should be printed by the function directly and the second argument tells it the desired size of the triangle. The triangle pattern should be largest in the middle row, thus two lines should be printed directly by functions that make recursive function calls. It may be desired to use another function to print the lines. For example calling the function as shown below, would print the output shown below it.

triangle(1, 5);

*
* *
* * *
* * * *
* * * * *
* * * *
* * *
* *
*

This problem will be discussed in class.

5.7.3. Dynamic Programming

For problems such as factorial and Fibonacci (Fib(n) = Fib(n-1) + Fib(n-2)) that return a fixed value based partly on recursive calls of lesser order, a global or static array might be used to save previously calculated values. Saving these values and later referencing them from the array rather than repeating recursive function calls can greatly improve the performance of recursive functions. This technique is called dynamic programming.

Note

There is actually a closed form (constant run time) solution to finding the Fibonacci sequence numbers, but it requires some mathematics not covered in this course. It is covered in the Data Analysis course. If you are curious see the notes from the Data Analysis study guide.

Footnotes

[1]

The last rule actually suggests that it is poor programming practice to solve simple recursive problems like n-factorial and computing the Fibonacci numbers by using recursion. However, just for the purpose of understanding recursion, we solve these problems recursively. Dynamic programming can significantly improve the performance for many problems.