Introductory Programming Lecture Notes: recursion

Recursion vs iterative functions

Recursive functions are simply functions that call themselves, while iterative functions are functions that do not call themselves.
For example, the following is a recursive function:
```
void foo(int x)
{
   ...
   foo(37);
   ...
}
```
As an example, we could use a recursive function to obtain and validate user input:
```
#include <cstdio>

int GetPositiveNumber();
// repeatedly prompt a user and read responses until a positive
//    integer is obtained, then return the integer

int main()
{
   int x;
   x = GetPositiveNumber();
   printf( "Obtained value %d\n", x);
}

int GetPositiveNumber()
// repeatedly prompt a user and read responses until a positive
//    integer is obtained, then return the integer
{
   // prompt user and read response
   printf( "Please enter a positive integer\n");
   numRead = scanf("%d", &data);

   // if nothing was read, the user entered non-integer data,
   //    read and diiscard it then call GetPositiveNumber
   //    again to obtain valid input
   if (numRead < 1) {
      scanf("%*s");
      printf("ERROR: that was not an integer\n");
      data = GetPositiveNumber();
   }

   // if response is invalid, then call the GetPositiveNumber
   //    function again to obtain valid input
   else if (data < 1) {
      printf( "ERROR: %d is not a positive integer\n", word);
      data = GetPositiveNumber();
   }

   return data;
}
```
Note on how results are computed:
- If the user gives a valid number on the first try, then the result is simply returned to main (where it gets printed out)
- Otherwise, the user gave an invalid number on the first try, an error message is displayed, and another call is made to GetPositiveNumber
  - The user gets prompted in this new call
  - If they enter a valid number at this point, then the value is returned to the first function, which then returns it to main, which then prints it out
  - Otherwise, the user has entered an invalid number on the second try, an error message is displayed, and yet another call is made to GetPositiveNumber
    - The user gets prompted again
    - If they enter a valid number at this point then the value is returned to the second GetPositiveNumber call, which returns it to the first GetPositiveNumber call, which returns it to main, which then prints it out
    - Otherwise, the user has entered an invalid number on the third try, an error message is displayed, and another call is made to GetPositiveNumber
      - etc. etc.

A typical structure for a recursive function is as follows:

return_type function_name(parameter list)
{
   if (completion condition) {
      computation to get the answer directly
   } else {
      computation plus recursive call
   }
   return value;
}

If the function has no "completion condition" then essentially it will be stuck in an infinite sequence of recursive calls: sooner or later you must compute an answer without needing to make yet another function call.

Generally speaking, the recursive call is made on a smaller, or simpler version of the problem.

For example, suppose we want to calculate factorials: N! = 1*2*3*...*N

In the simplest cases, where N is 1 or 2, N! equals N
For cases where the value of N is greater than 2, we know that N! = (1*2*...*(N-1))*N, i.e. N! = (N-1)! * N
Thus, if we knew the value of (N-1)! we could use it to calculate the value of N!

This leads to the following code:

int factorial(int N)
{
    int result;

    if (N <= 2) {
       result = N;
    } else {
       result = factorial(N-1) * N;
    }
    return result;
}

Note that we have a quitting condition - for the cases where it is simple to calculate the result without making a recursive call - and a recursive call (plus a little extra computation) to calculate the more "difficult" cases.

When we make a call like x = factorial(5);
what sequence of calls occurs?

factorial(5)
    factorial(4)
        factorial(3)
            factorial(2)

at this point the values are passed "back up the line"

 - i.e. factorial(2) returns 2
             then factorial(3) returns 6
                  then factorial(4) returns 24
                       then factorial(5) returns 120

Recursion: advantages and disadvantages

The main advantage of recursion is that it is often clearer to read and understand, giving shorter code
The main disadvantage of recursion is efficiency
Although the source code may be shorter, when it runs it may involve a great many recursive calls
Function calls themselves tend to be slow: a typical function call may take ten times as long to execute as an integer addition statement
Function calls also take up memory - each time you call a function it sets aside space for local variables and a small block of other information
Thus iterative functions are often more efficient in running time and use of memory, but are sometimes more difficult to code correctly

Other recursion examples

Calculating Fibonacci numbers: the Fibonacci numbers are defined as follows:

Fibonacci(1) = 1
Fibonacci(2) = 1

For N > 2, Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2)

Fibonacci(3) = Fibonacci(1) + Fibonacci(2) = 1 + 1 = 2
Fibonacci(4) = Fibonacci(2) + Fibonacci(3) = 1 + 2 = 3
Fibonacci(5) = Fibonacci(3) + Fibonacci(4) = 2 + 3 = 5
Fibonacci(6) = Fibonacci(4) + Fibonacci(5) = 3 + 5 = 8
Fibonacci(7) = Fibonacci(5) + Fibonacci(6) = 5 + 8 = 13
etc.

Recursive function to calculate Fibonacci numbers:

int fibonacci(int N)
{
  int x, y;
  if (N < 3) { // simple completion case
     return 1;
  } else {
     // recursive case
     x = fibonacci(N-1);
     y = fibonacci(N-2);
     return x + y;
  }
}

Suppose in main we make the function call x = fibonacci(4);
what happens during execution?

in the call to fibonacci(4)
   4 is not < 3, so we perform the recursive calls:
   x = fibonacci(3)
       in the call to fibonacci(3)
          3 is not < 3, so we perform the recursive calls:
          x = fibonacci(2)
              in the call to fibonacci(2)
                 2 < 3, so we return 1
          i.e. x = 1
          y = fibonacci(1)
              in the call to fibonacci(1)
                 1 < 3, so we return 1
          i.e. y = 1
          return 1 + 1
   i.e. x = 2
   y = fibonacci(2)
       in the call to fibonacci(2)
          2 < 3, so we return 1
   i.e. y = 1
   return 2 + 1
i.e. fibonacci(4) returns 3

Palindrome checking: examining a string (array of characters) to see if it reads the same forwards as backwards

A palindrome is a string that reads the same forward and backward, e.g. "rotator", "dad", "blah foooof halb", etc.
We can recursively define palindromes by noting that a string contained in array str is a palindrome if the following two conditions hold:
- the first character in str matches the last character in str,
- the string between the first and last characters of str is a palindrome

That leads to the following palindrome-testing function:

Boolean palindromecheck(string str, int first, int last)
{
   // check if you're down to 0 or 1 characters
   if (last <=first) {
       return(true);
   }

   // check if first char matches last char
   else if (str[first] != str[last]) {
       return(false);
   }

   // ok so far, check the string in the middle
   else {
      return(palindromecheck(str, first+1, last-1));
   }
}

The initial call would look something like

result = palindromecheck(mystring, 0, size-1);

Suppose we start out with mystring set to "argra", with size == 5, what would the execution sequence look like?

on the first call to palindromecheck, first = 0, last = 4
   last > first, so we don't return true
   mystring[0] is 'a', and mystring[4] is 'a',
        so we don't return false
   make recursive call to palindromecheck with first = 1, last = 3
        last > first, so we don't return true
        mystring[1] is 'r', and mystring[3] is 'r',
             so we don't return false
        make recursive call to palindromecheck with first = 2, last = 2
             last == first, so return true
   return result of recursive call, i.e. return true
return result of recursive call, i.e. return true

Binary search: searching a sorted array of values for one specific value:
- Suppose we are given an array of numbers, and the values are all in sorted order
  Now suppose we are given another number, N, and asked to determine if N is in the array, and if so where?
  Binary search proceeds as follows:
  - Look in the middle of the array
  - If N is the element stored there then you are done
  - If N is less than the element in the middle of the array then you know it must be somewhere in the first half of the array, so make a recursive call to search the lower half of the array
  - If N is greater than the element in the middle of the array then you know it must be somewhere in the second half of the array so make a recursive call to search the upper half of the array
- To get the recursive process to work, we need to pass the following parameters to the function:
  - the array of elements
  - the number we are looking for (often referred to as the key)
  - two values that represent the section of the array we need to search: originally these will be the first and last positions of the array, then after the first call they will indicate which half of the array, then after the second call they will indicate which quarter of the array, etc etc until we are down to a single element (which either is or is not the key)
```
int binarysearch(float arr[], float key, int low, int high)
// low and high indicate the boundaries of the portion
// of the array we still need to search
//
// binarysearch returns -1 if the key is not found in arr[],
// otherwise it returns the array index at which the key was found
{
   int middle; // used for computing the midpoint of the
               // section we still need to search

   if (high < low) {
      return(-1); // key not found, no space left to search
   }

   // find middle of array and check for key
   middle = (high + low) / 2;
   if (key == arr[middle]) {
      return(middle); // got lucky and found the key
   }

   // if key not found, make recursive call to search 
   //    upper half or lower half, ass appropriate
   else if (key < arr[middle]) {
      // key is less than middle element, so
      // search the lower half of the current section
      return(bsearch(arr, key, low, middle-1);
   } else {
      // key is greater than middle element, so
      // search the upper half of the current section
      return(bsearch(arr, key, middle+1, high);
   }
}
```
- The initial call might look like
```
int keypos;
float key;
float myarray[size];

// do something to initialize myarray and key values

keypos = binarysearch(myarray, mykey, 0, size-1);
```

Towers of Hanoi

Suppose we have 3 pegs and a set of different sized disks with holes in the middle.
The disks sit on the pegs (the pegs go through the holes) but you are never allowed to put a smaller disk on top of a larger one.
The problem is as follows, if there are N disks on one peg, how can you legally move them to another peg?
(Try it with 5 or 6 disks, it's tougher than it looks!)

There is a simple recursive program that will tell you the order in which to move things:

#include <cstdio>

void  hanoi(int n, char source, char goal, char spare);

int main()
{
   int disks;
   printf( "We have 3 pegs, called A, B, and C\n");
   printf( "In the beginning all the disks will be on peg A\n");
   printf( "The task is to legally get them all moved to peg B\n");
   printf( "How many disks do you want to move?\n");
   scanf("%d", &disks);
   printf( "The correct sequence of moves is as follows:\n");
   hanoi(disks, 'A', 'B', 'C');
}

void  hanoi(int n, char source, char goal, char spare)
{
   if (n == 1) {
      printf( "Move disk from %c", source);
      printf( " to %c\n", goal);
   } else {
      hanoi(n-1, source, spare, goal);
      printf( "Move top disk from peg %c", source);
      printf( " to peg %c\n", goal);
      hanoi(n-1, spare, goal, source);
   }
}