Fibonacci

Often it is wise in coding to deal gracefully with bad data. Let us do this by adding two error cases.

 Fib( 1 ) == 1
 Fib( 2 ) == 1
 Fib( n ) == Fib(n-1) + Fib(n-2)
 
 // error conditions
 Fib( 0 ) == 0
 Fib( negative integer ) == 0
 

Here is a structured recursive version that follows this description

long Fib( long n )
{
  long val;
  
  /* error */
  if ( n<=0 ) 
    val = 0;
  
  /* base cases */
  else if ( n==1 || n==2 ) 
    val = 1;
  
  /* recursive case */  
  else
    val =  Fib( n-1) + Fib( n-2 ); 
    
  return val;
}

Here is a early-return recursive version that follows this description

long Fib( long n )
{
  /* error */
  if ( n <= 0 ) return 0;
  
  /* base cases */
  if ( n==1 || n==2 ) return 1;
  
  /* recursive case */  
  return Fib( n-1 ) + Fib( n-2 ); 
}

Most programmers would prefer the early-returns version.

If you truly needed the Fibonacci series for some reason (it occurs in the solution of some differential equations, for example), you would likely use iteration to get it. Here is an early-returns iterative version:

long Fib( long n )
{
  int j, sum,  back1, back2;
  
  /* error */
  if ( n <= 0 ) return 0;
  
  /* base cases */
  if ( n==1 || n==2 ) return 1;
  
  back2 = 1; back1 = 1; sum = 0; 
  for ( j=3; j<=n; j++ )
  {
    sum = back1 + back2;
    back2 = back1;
    back1 = sum;
  }
  
  return sum;
}