# Recursion to Iteration: Fibonacci Sequence

The Fibonacci sequence consists of these numbers {0, 1, 1, 2, 3, 5, 8, 13, 21, 34…}. Intuitively, one can see that the next number in the sequence will be a summation of the current number and the previous number. The Fibonacci sequence written recursively is:

```public static int fibRecursive(int n) {
if(n < 0){
throw new IllegalArgumentException("n < 0");
}
if (n <= 1)
return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}```

Behind the scenes, each recursive function call gets pushed on the stack as a stack frame therefore we can emulate recursion calls using a stack:

```public static int fibUsingStack(int n) {
if(n < 0){
throw new IllegalArgumentException("n < 0");
}
Stack<Integer> stack = new Stack<>();
stack.push(n);
int sum = 0;
while (!stack.empty()) {
Integer next = stack.pop();
if (next == 0 || next == 1) {
sum += next;
continue;
}
stack.push(next - 2);
stack.push(next - 1);
}
return sum;
}```

This is just a fun learning exercise which helps create understanding on how to convert recursive functions to iterative functions. It wouldn’t make sense to use a stack for this use case.