Consider the recursive function for calculating the nthFibonacci number: int fib

Question

Consider the recursive function for calculating the nthFibonacci number:
int fib(int n) {

   if (n == 0)
      return 0;

   else if (n == 1)
      return 1;

   else
      return fib(n-1) + fib(n-2);
}

(b) In what situations will thefunction terminate? How do you know that it will terminate inthose circumstances?

Explanation / Answer

1) It will terminate when n= ZERO....since thefunction fib(0) returns 0 2) It terminates when n=1...as fib(1)returns 1 3) It will also terminate for every positive integern>1        For every positive numbergreater than one, (n-1) will be a positive integer and(n-1) is either zero or positive integer. The functionfib() will be called on n-1 andn-2 recursively. Eventually the calls will come tofib(1) or fib(0). As fib(0) and fib(1) terminate, fib(n) also terminates 4) For integers n

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---