Java

TOPIC 33 – RECURSION

LESSON GROUP WORK

QUESTION 1 (GROUP WORK)

Together, we will implement and test the factorial function. We will implement it in a traditional way using a loop. And we will implement it using recursion.

QUESTION 2 (GROUP WORK)

We will implement the famous Fibonacci Numbers function in java. This function is perhaps the most popular recursive function and is defined by the following:

fib(n) = fib(n-1) + fib(n-2) for all n > 2

fib(2) = 1

fib(1) = 1

a) Come up with the first 10 Fibonacci numbers. This is easy enough to do if you are gradually working your way up.

b) Write the function that will calculate the n^th Fibonacci number. You will have to make use of recursion. Thankfully, once we have the recusive definition, it is very easy to translate that to Java code.

c) In a main method, test your method inside a loop. What is the 25^th Fibonacci number?

d) Describe the response time of the computer when calculating larger numbers Fibonacci numbers such as fib(40).