Question

Provide a recursive definition of some sequence of numbers or function (e.g. log, exponent, polynomial). Choose one different from that of any posted thus far. Write a recursive method that given n, computes the nth term of that sequence. Also provide an equivalent iterative implementation. How do the two implementations compare?

Answer 1

CODE

public class Main {

public static int fibonacciIterative(int n) {

if(n <= 1) {

return n;

}

int fib = 1;

int prevFib = 1;

for(int i=2; i<n; i++) {

int temp = fib;

fib+= prevFib;

prevFib = temp;

}

return fib;

}

public static int fibonacciRecursive(int n) {

if(n <= 1) {

return n;

}

return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);

}

public static void main(String args[]) {

System.out.println("Fibonacci numbers using iteration: ");

for (int i=1; i<=10; i++) {

System.out.print(fibonacciIterative(i) + " ");

}

System.out.println();

System.out.println("Fibonacci numbers using recursion: ");

for (int i=1; i<=10; i++) {

System.out.print(fibonacciRecursive(i) + " ");

}

}

}