The Fibonacci numbers are a famous sequence which shows up in many problems. The

Question

The Fibonacci numbers are a famous sequence which shows up in many problems. The sequence, which starts 1, 1, 2, 3, 5, 8, 13, 21, 34, ... is computed by setting each term to the sum of the previous two terms. In a recursive definition, we have fib(1) = 1, fib(2) = 1, and fib(n) = fib(n-1) + fib(n-2) in general.

Write a recursive method which computes the n-th Fibonacci number. Use "long" for the return value and write a simple test driver. You should definitely be able to compute fib(25). Even fib(50) might take longer to compute than you're willing to wait.

Explanation / Answer

As per definition, we can build pseudeo-code for calculating the n-th Fibonacci number as:

fib ( n ) {
  if n <= 2 {
   return 1;
  }
  return fib(n-1) + fib(n-2);
}

This method recursively computes the sequence. In C, the corresponding code would look like this:

#include <stdio.h>

long fib( int n ) {
   if( n<=2 ) return 1;
   return fib(n-1) + fib(n-2);
}

// now the driver code...
int main() {
   printf("%ld ", fib(1));
printf("%ld ", fib(2));
printf("%ld ", fib(3));
printf("%ld ", fib(5));
   printf("%ld ", fib(25));
   printf("%ld ", fib(50));
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.