Page History

...

Non-Compliant Code Example

This is a naive implementation of the Fibonacci function using exponential recursion (as well as exponential time). When tested on a Linux system, fib1(100) crashes with a segmentation fault.

int fib1(unsigned int n)
{
  if (n == 0)
    return 0;
  else if (n == 1 || n == 2)
    return 1;
  else
    return fib1(n-1) + fib1(n-2);
}

Compliant Solution

This is a much more efficient solution, using constant space and linear time. Tested on a Linux system, fib2(100) is calculated almost instantly and with almost no chance of crashing due to a failed stack allocation.

int fib2(unsigned int n)
{
  if (n == 0)
    return 0;
  else if (n == 1 || n == 2)
    return 1;

  unsigned int prev = 1;
  unsigned int cur = 1;

  int i;
  for (i = 3; i <= n; i++)
  {
    int tmp = cur;
    cur = cur + prev;
    prev = tmp;
  }

  return cur;
}

...