See last two text boxes for C# Code.

Welcome to Recursion Lab 3. In this lab you will write an application the will return to the user the number of Fibonacci sequence they request. For example, in order to step through each Fibonacci number up to the fifth you would perform the following calculation, 1+1=2+1=3+2=5 (the highlighted numbers are each of the successive Fibonacci numbers). As you can see the Fibonacci sequence always begins with ones and then after words proceeds with the sequence. For this application, you will need to be able to ascertain the ith Fibonacci number. Here’s the formula you will need:

Fibo(i) = Fibo(i-1)+Fibo(i-2);

By using this formula you will be able to move closer to the termination point, which for this application will be when a 1 or a 2 is passed into the procedure.  The above formula allows you to calculate the i^th element of the Fibonacci sequence. It is also supposed to allow you to predict the growth in the rabbit population for the i^th month by adding the i^th – 1 month’s growth in the rabbit population to the i^th – 2 month’s growth in the rabbit population.  Now that you know the background of the formula and what it is supposed to calculate, let’s step through an example.  For simplicity sake, we will use 4 as the i^th Fibonacci number we are trying to calculate, as shown below:

Fibo (4) = Fibo(4-1)+Fibo(4-2);

Notice that the procedure is called again, this time the values 3 and 2 will be passed (since the value 4 was decremented by 1 and 2), and should look similar to the following:

Fibo (4) = Fibo(4-1)+Fibo(4-2); Fibo (3) = Fibo(3-1)+Fibo(3-2); Fibo (2) = Fibo(2-1)+Fibo(2-2);

As you can see, on the last call i was equal to 2, one of the terminating conditions. Also, as you see for the second equation in the example above, the one that calculates the Fibonacci of 3, we need to break it down into 2 formulas as shown below:

Fibo (4) = Fibo(4-1)+1; Fibo (3) = Fibo(3-1)+Fibo(3-2); Fibo (2) = 1 //calculates the Fibonacci of 3 Fibo (2) = Fibo(2-1)+Fibo(2-2); Fibo (1) = Fibo(2-1)+Fibo(2-2);

As you can see from the example above, when we continue on with the calculation of the Fibonacci of 3, it sends a 1 and a 2 to the next iteration of the formula which means that it is done since when we get a 2 or 1, our terminating condition. The formula would look similar to the following:

Fibo (4) = Fibo(4-1)+1; Fibo (3) = 1+1 Fibo (2) = 1 //calculates the Fibonacci of 3 Fibo (2) = 1 Fibo (1) = 1

Now that the calculation for the Fibonacci of 3 is complete, we can send it back to the equation that called it and get the result. The formula looks similar to the following:

Fibo (4) = 2 + 1 = 3 Fibo (3) = 1+1 = 2 Fibo (2) = 1 Fibo (2) = 1 Fibo (1) = 1

As you can see from the above calculation, the fourth number in the Fibonacci sequence is 3. 

Let’s go ahead and code the application.

Prompt the user for the number of the Fibonacci sequence that he/she would like to see. Call the procedure (we’ll fill in the code later). Your code should look similar to the following:

static void Main(string[] args) { int i; int fibonnacciNum; Console.WriteLine("Please enter a number: "); i = Convert.ToInt32(Console.ReadLine()); fibonnacciNum = Fibo(i); Console.WriteLine("The answer is " + fibonnacciNum); Console.ReadLine(); }

Now that your application can prompt for, take in, and pass input to the procedure you will be using, it is time to code the procedure.  For this application you will need to set the terminating condition to if (i == 1 || i == 2) so the procedure will terminate when it receives a 1 or a 2. After you coded the conditional statement that sets up the terminating condition, you will need to either store and return, or just return the results of the procedure’s computations to the main algorithm. If the terminating condition is met, return a 1 to the calling procedure, if it is not met, return the value of the calculation. Your code should look similar to the following:

namespace ConsoleApplication1 { class Program { public static int Fibo(int i) { int ans; if (i = = 1 || i = = 2) { ans = 1; } else { ans = Fibo(i - 1) + Fibo(i - 2); } return ans; } static void Main(string[] args) { int i; int fibonnacciNum; Console.WriteLine("Please enter a number: "); i = Convert.ToInt32(Console.ReadLine()); fibonnacciNum = Fibo(i); Console.WriteLine("The answer is " + fibonnacciNum); Console.ReadLine(); } } }

Compile and run your code. Your output should be similar to this:

Congratulations, you have completed writing the Fibonacci sequence!