Recursion - Advanced Topics in Java: Core Concepts in Data Structures - page 143

We can write hcf as a recursive Java function like this:
public static int hcf(int m, int n) {
if (n == 0) return m;
return hcf(n, m % n);
}
As a matter of interest, we can also write hcf as an iterative (as opposed to recursive) function, using Euclid's
algorithm. Here it is:
public static int hcf(int m, int n) {
int r;
while (n > 0) {
r = m % n;
m = n;
n = r;
}
return m;
}
Effectively, this function does explicitly what the recursive function does implicitly.
Yet another example of a recursively defined function is that of the Fibonacci numbers. We define the first two
Fibonacci numbers as 1 and 1 . Each new number is obtained by adding the previous two. So, the Fibonacci sequence
is as follows:
1, 1, 2, 3, 5, 8, 13, 21, and so on.
Recursively, we define the n th Fibonacci number, F(n) , as follows:
F(0) = F(1) = 1
F(n) = F(n - 1) + F(n - 2), n > 1
This is a Java function to return the n th Fibonacci number:
public static int fib(int n) {
if (n == 0 || n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
Again, we emphasize that while this function is neat, concise, and easy to understand, it is not efficient.
For example, consider the calculation of F(5) :
F(5) = F(4) + F(3) = F(3) + F(2) + F(3) = F(2) + F(1) + F(2) + F(3)
= F(1) + F(0) + F(1) + F(2) + F(3) = 1 + 1 + 1 + F(1) + F(0) + F(3)
= 1 + 1 + 1 + 1 + 1 + F(2) + F(1) = 1 + 1 + 1 + 1 + 1 + F(1) + F(0) + F(1)
= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 8
Notice the number of function calls and additions that have to be made, whereas we can calculate F(5)
straightforwardly using only four additions. You are urged to write an efficient, iterative function to return the n th
Fibonacci number.