Practice examples: recursion

    Recursion: any function that calls itself is called recursive (all other functions are referred to as non-recursive).

  1. Example 1: Error checking Some of the error checking functions we wrote were recursive, e.g. 
    int getPositiveInteger()
{
   // prompt the user
   printf("Please enter a positive integer\n");

   // read in the value
   int value;
   scanf("%d", &value);

   // if it is valid return it
   if (value > 0) return value;

   // otherwise 
   //    give an error message
   //    call the function again
   //    store what comes back and return it
   else {
      printf("Error: %d was not a positive integer\n", value);
      value = getPositiveInteger();
      return value;
   }
}

  2. Example 2: problem solving Recursion is a common problem solving technique, and usually involves testing for a simple case (where we can just compute/return a value) and otherwise making the recursive call and returning the result.

    In the example below we sum the contents of an array from array positions 0 through N-1. The 'simple' (or 'base') case is where N is less than 1, where all we need to do is return 0 (don't sum anything). For all other cases we make a recursive call to get the sum of the previous N-1 elements and add the current element to the result (returning that). 
    int sumArray(int arr[], int N)
{
   int value;
   // simplest case, sum nothing
   if (N < 1)
      value = 0;
   } else {
      // call the function to sum the previous N-1 elements
      value = sumArray(arr[], N-1);
      // and add the Nth element to that
      value = value + arr[N-1];
   }
   // return the result
   return value;
}

  3. Example 3: in this example we recursively search for the smallest element in the first N positions in an array 
    int smallest(int arr[], int N)
{
   int result
   if (N == 1) result = arr[0];
   else {
      // compare smallest thing from first N-1 elements
      // to the Nth element, return whichever is smaller
      result = smallest(arr, N-1);
      if (result > arr[N-1]) result = arr[N-1];
   }
   return result;
}

  4. Example 4: Computing the Nth fibonacci number
    The first two fibonacci numbers are defined as 0 and 1, all subsequent fibonacci numbers are defined as the sum of the previous two. Thus the fibonacci sequence goes 0, 1, 2, 3, 5, 8, 13, 21, 34, etc. 
    int fibonacci(int N)
{
   if (N <= 0) return 0;
   else if (N == 1) return 1;
   else return (fibonacci(N-1) + fibonacci(N-2));
}

  5. EXERCISE Write a main routine that calls each of the functions below, record the output and make sure you can explain how/why the sequence of calls and returns happen the way they do. 

    int getPositiveInteger()
{
   static int count = 0;  
   count++;
   printf("Entering getPosInt call %d\n", count);
   printf("Please enter a positive integer\n");
   int value, result;
   scanf("%d", &value);
   if (value > 0) result = value;
   else {
      printf("Error: %d was not a positive integer\n", value);
      result = getPositiveInteger();
   }
   printf("Leaving getPosInt call %d", count);
   printf(", returning %d\n", result);
   return result;
}

    int sumArray(int arr[], int N)
{
   int value;
   printf("In sumArray, N = %d\n", N);
   if (N < 1)
      value = 0;
   } else {
      value = sumArray(arr[], N-1);
      value = value + arr[N-1];
   }
   printf("In sumArray, N = %d", N);
   printf(", returning %d\n", value);
   return value;
}

    int smallest(int arr[], int N)
{
   int result
   printf("In smallest, N = %d\n", N);
   if (N == 1) result = arr[0];
   else {
      result = smallest(arr, N-1);
      if (result > arr[N-1]) result = arr[N-1];
   }
   printf("In smallest, N = %d", N);
   printf(", returning %d\n", result);
   return result;
}

    int fibonacci(int N)
{
   int value = 0;
   if (N <= 0) value = 0;
   else if (N == 1) value = 1;
   else {
      printf( "inside call fib(%d), calling fib(%d)\n", N, N-1);
      value = fibonacci(N-1);
      printf("inside call fib(%d), calling fib(%d)\n", N, N-2);
      value += fibonacci(N-2);
   }
   printf("call fib(%d) completing\n", N);
   return value;
}

  6. EXERCISE
    Examine the following program and the output it produces, then explain as clearly as possible how/why that precise output is produced. 
     original program
#include <cstdio>

int f1(int a);
int f2(int b);

int main()
{
   printf("main: %d\n", f1(2));
}

int f1(int a)
{
   int result = a;
   printf("entering f1: %d\n", result);
   if (a >= 0) result = f2(a+1);
   printf("leaving f1: %d\n", result);
   return result;
}

int f2(int b)
{
   int result = b;
   printf("entering f2:%d\n", result);
   if (b >= 0) result = f1(b-2);
   printf("leaving f2:%d\n", result);
   return result;
}

    output produced
entering f1:2
entering f2:3
entering f1:1
entering f2:2
entering f1:0
entering f2:1
entering f1:-1
leaving f1:-1
leaving f2:-1
leaving f1:-1
leaving f2:-1
leaving f1:-1
leaving f2:-1
leaving f1:-1
main:-1