Question

Design a simple program, using pseudocode, to implement the recursive formula you found in part (a) to compute numbers in the Fibonacci sequence. Describe in detail how your program implements the recursive formula. You may find it useful to discuss how it through a concrete example such as F(8) = 21.

Answer 1

Program:

import java.util.Scanner;

public class fibonacci {
   public static long fib(long n) {
   if ((n == 0) || (n == 1))
   return n;
   else
   return fib(n - 1) + fib(n - 2);
   }
   public static void main(String[] args) {
       long num;
  
       Scanner sc= new Scanner(System.in);
       System.out.println("Enter the number=");
       num=sc.nextLong();
       System.out.println("The Fibonacci number at "+num+" position is, F["+num+"] = "+fib(num));
          
   }
   }

Console output:

Enter the number=
8
The Fibonacci number at 8 position is, F[8] = 21

Explanation:

For F[8]= series look like:

0

1

1

2

3

5

8

13

21

The method fib() calculates the fibonacci number at position n. If n is equal to 0 or 1, it returns n as when user enter 0 or 1 it can give the answer as respective to their values.. Otherwise it recursively calls itself and returns fib(n - 1) + fib(n - 2). A code for this is defined in fib() function.

In main(), the method fib() is called when the user enters the number of his/her choice. A code for this is defined in main() function.

Eg: Let user enters the num =5

fib(5), this will call the fib function.

Function has the parameter value of 5.

It checkes the condition whether num = 0 or 1, if not then move to else conditon

in else again fib function is called with its decremented values.

So, the tree is formed and looks like this during execution,

Program snap shot:

output 1:

output 2:

output 3: