auto-posted gist

fibDemo.c

#include <stdlib.h>
#include <stdio.h>

long fibonacci(int n) {

  if(n == 0 || n == 1) {
    return 1l;
  } else {
    return fibonacci(n-1) + fibonacci(n-2);
  }

}

void countDown(int n) {

    if(n < 0) {
      printf("Error: cannot count down from negatives!");
    } else if(n == 0) {
      printf("Blast Off\n");
    } else {
      printf("%d\n", n);
      countDown(n-1);
    }
    return;
  }

int main(int argc, char **argv) {

  if(argc != 2) {
    fprintf(stderr, "Usage: %s n \n", argv[0]);
    exit(1);
  }
  int n = atoi(argv[1]);
  long x = fibonacci(n);
  printf("fibonacci(%d) = %ld\n", n, x);
  return 0;
}

memoization.c

#include <stdlib.h>
#include <stdio.h>

long fibonacci(int n, long *fibTable) {

  //fibonacci(n) has already been computed, use it:
  if(fibTable[n] != 0) {
    return fibTable[n];
  } else {
    //fibonacci(n) has NOT yet been computed, so "pay" for the recursion:
    long x = fibonacci(n-1, fibTable) + fibonacci(n-2, fibTable);
    fibTable[n] = x;
    return x;
  }

}

int main(int argc, char **argv) {

  if(argc != 2) {
    fprintf(stderr, "Usage: %s n \n", argv[0]);
    exit(1);
  }
  int n = atoi(argv[1]);

  //1. Initialize a cache of values to be stored
  //   fibTable = [1, 1, 2, 3, ..., n]
  long *fibTable = (long *) malloc(sizeof(long) * (n+1));
  //2. Initialize the values in fibTable to "flag" values that indicate 
  //   the *real* value has not yet been computed
  for(int i=0; i<n+1; i++) {
    fibTable[i] = 0;
  }  
  //3. Initialize your base cases
  fibTable[0] = 1;
  fibTable[1] = 1;
  for(int i=2; i<=n; i++) {
    fibTable[i] = fibTable[i-1] + fibTable[i-2];
  }  
  //long x = fibonacci(n, fibTable);
  long x = fibTable[n];
  printf("fibonacci(%d) = %ld\n", n, x);
  return 0;
}

recursion.md

CSCE 155E - Computer Science I

Recursion

• What is recursion?
• In general, recursion is something that references itself
• Example: fractals
• Fibonacci sequence:

$$\begin{equation*} f(n) = \begin{cases} 1 & n = 0\\ 1 & n = 1\\ f(n-1) + f(n-2) & \text{otherwise} \end{cases} \end{equation*}$$

$$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots$$

• Recursion in coding refers to a function that makes calls to itself!
• Motivating example: print a count down from 10 to 1 (then "blast off") without using a loop!

void countDown(int n) {

  if(n == 0) {
    printf("blastoff!\n");
  } else if(n > 0) {
    printf("%d\n", n);
    countDown(n-1);
  }

}

countDown(10);

• Recursive functions have several aspects:

  • Base case: it is a condition or case in which the recursion stops (ie no more recursive calls are made)
  • Each recursive calls must make some progress toward the base case
  • Corner cases may need to be handled separately

• A recursive function is simply a function that makes one or more recursive calls to itself

• Deep or infinite recursions may result in stack overflows

• Recursion can be a "good" and "useful" tool

  • Many divide and conquer algorithms use recursion
  • Many programming languages use recursion as a fundamental control flow mechanism

• Problems:

  • Recursive functions essentially abuse the stack space by creating stack frames
  • Deep or infinite recursions can lead to stack overflow
  • Any recursive function can be rewritten as a non-recursive function
  • Recursion can often be simulated using an in-memory stack
  • Some organizations even ban the use of recursion (NASA)
  • Recursion risks needlessly recomputing the same values over and over (Fibonacci)

• Eliminating Recursion

  • You can always rewrite a recursive function using non-recursive code
  • You can use an in-memory stack to simulate recursion
  • You can use tail recursion and rely on the compiler to optimize your recursion away
  • You can use memoization
  • Idea: you want to avoid repeated computations of the same value
  • YOu "pay" for the recursion if you have not already computed the value
  • Once you've paid for the recursion, you store ("cache") the result
  • Subsequently instead of making a recursive call, you check the cache: if it has already been computed, you use it and do not make a recursive call!
  • Demonstration in C: use memoization to compute the fibonacci number, eliminating redundant recursive calls

• Hack 12: you'll also use memoization to compute the binomial coefficients: $${n \choose k}$$

• This is the number of ways to choose $k$ elements from a set of size $n$

• Example: given 25 baseball players, you need to choose 9 of them to start a game, the number of ways to do this is: $${25 \choose 9} = \frac{25!}{(25-9)!9!}$$

• Pascal Identity: $${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$$