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.