Recursion

What is recursion?

All recursive algorithms are based on the idea that if we keep dividing a problem into problems of a smaller size, then eventually we'll get to a problem (or problems) which is so small that the solution for it is trivial. Such small problem is called a base case. There may be recursive algorithms with one or several base cases.

In programming, a recursive algorithm is usually implemented by a recursive function, i.e. a function that makes a call to itself. A recursive function must have a base case (or base cases), otherwise it will be looping forever. However, even having a base case does not guarantee that recursion always stops: one has to check that the function reaches a base case for all arguments.

How to solve a problem recursively.

1. Think of a way of breaking the problem into smaller problems. Now assume that all or some of these problems are already solved. Can you construct the solution of the whole problem from solution(s) of the smaller problem(s)? If yes, then this is a potential recursive solution.
2. Take the potential recursive solution and check that the size of the problem gets smaller with every iteration. For this you need to figure out what is the size of the problem that you are solving.
3. Figure out what are the base cases. Check that the algorithm reaches a base case for any input.
4. Write down your algorithm on paper and test it for several cases.
5. Write the implementation of your algorithm in C++ or other programming language, test it on several inputs to make sure that it works in all cases. Choose inputs that are different from one another (for instance, use both odd and even numbers, small and large numbers, etc.)

A simple example: computing a power of a number.

1. We notice that if we already know the value of b**(e-1) (b raised to the power e - 1), then we can get the value of b**e by multiplying b**(e-1) by b.
2. If we take e to be the size of the problem, then the size of the problem reduces by 1 on every iteration.
3. Base case: if e equals 1, then b**e is just b. Since e reduces by 1 on every step, then eventually it will reach 1, no matter what the initial value was.
4. The algorithm will look something like this:

       To compute b raised to the power e:
       Base case: if e is 1, return b.
       Recursive step: if e > 1, multiply b by b raised to the power e-1. 
   

   Test algorithm for b = 2 and e = 3:

       (2 raised to the power 3) = (2 multiplied by (2 raised to the power 2))
       = (2 multiplied by (2 multiplied by (2 raised to the power 1))) =
       = (2 multiplied by (2 multiplied by 2)) = 2 * 2 * 2 = 8. 
   

5. The C++ function implementing the algorithm is:

   int power (int base, int exponent)
   {
     if (exponent == 1)
       return base;
     else 
       return base * power(base, exponent - 1);
   }
   

   The function can be easily tested using he program test.cpp.

Assignment for this lab.

Palindrome problem.

Ideas for the algorithm.

Is the part of the word that you need to know shorter than the whole word? By how many letters?

What would you suggest for base case(s)?

In which case can you easily tell that a word is not a palindrome?

Let us try to write down the algorithm (not C++ code yet) and test it on words "noon", "common", "eve", "rear". Can you think of other good test examples?

Writing code for IsPalindrome(char str[], int length)

Important: the function IsPalindrome takes two arguments: a string (i.e. an array of characters without the string termination constant \0) and the length of the string. The reason why we need to pass the length of the string as an argument is that the string passed to a function is only part of a word, i.e. it does not end with the string termination character, and so we can not use the function strlen inside IsPalindrome to determine the length of the string (strlen works only for strings that end with \0). Make sure that you pass the correct value as the length of the string.

When you have written the code, compile it with the command

g++ -Wall -o recursion recursion.cpp

Testing the program

Question 1. Show (on paper) how the program works on words "radar" and "river". How many function calls are made for each of these words?

Question 2. What are base cases of the function? Why are these cases sufficient?

Running the program on the dictionary file: fun part of the lab :-)

    recursion < /usr/share/lib/dict/words

    recursion < file name

    while (cin >> word) { ... }