## Example of recursive code without an exit condition

Let's take another look at a recursive problem. As an example, consider calculating Fibonacci numbers. Everybody will recall that the Fibonacci sequence is a numerical sequence in which the first two numbers are 0 and 1, and each subsequent number is equal to the sum of the two previous numbers.

Let's write code to calculate and display these numbers:

``````
public class Fibonacci {
public static void main(String[] args) {
System.out.println(0);
System.out.println(1);
printFibonacci(0, 1);
}

private static void printFibonacci(long penultimate, long previous) {
long current = penultimate + previous;
System.out.println(current);
printFibonacci(previous, current);
}
}
``````

Before the first call of the recursive printFibonacci method, print the first two numbers of the sequence: zero and one. We need to do this because the recursive method displays only the sum of the input parameters, not the parameters themselves.

The code looks okay: we get two numbers, calculate their sum, print it on the console, and call the printFibonacci method recursively again. We pass the previous number (previous) and the current number (current) as arguments.

Actually, the code has two errors. You can see them if you run the code.

The first error is overflowing the long type. The 104th number in our sequence is negative, indicating that the long type overflowed.

The second error is different. After calculating roughly 12,000 numbers, we get:

Now is an appropriate time to recall what a method call stack is in Java. The Java machine keeps a record of all function calls. To do this, it uses a special kind of collection called a stack. When one function calls another, the Java machine pushes a new StackTraceElement onto the stack. When the function ends, this element is removed from the stack. Accordingly, the stack always stores up-to-date information about the current state of the function call stack. The documentation for StackTraceElement says that it is "Thrown when a stack overflow occurs because an application recurses too deeply." A running JVM has a special area of memory for storing the method call stack. The size of this memory area depends on the OS and JVM settings. In addition to the method call stack itself, primitive variables (specific values of method parameters) and the addresses of reference variables (in a memory area called the "heap") are stored in this special memory area. Access to the call stack follows the LIFO principle.

## Corrected example with an exit condition

Let's start by fixing the second problem in the code.

Let's try to solve the problem head-on: if the stack is too small, then let's make it bigger. To do this, start the JVM with the "-Xss" flag and specify how much memory to allocate for the stack. Let's try allocating 5 megabytes. This is what it will look like in IDEA:

We managed to increase the length of the output. Now can calculate more than 49,000 numbers of the sequence rather than being limited to about 12,000 numbers. But at some point, we still get a StackOverflowError.

You can try to increase the size of the stack, but that doesn't fix the fundamental problem. So, let's look for a problem in logic. There must be a point when the recursion stops. In other words, there must be some condition that determines when the recursive method will no longer be called, allowing the call stack to unwind. To define such a condition, let's make our objective explicit: display the Fibonacci series as long as its numbers are less than Integer.MAX_VALUE.

Let's write a new printFibonacciWithCondition method that will take this condition into account. And we will call the new corrected method in the main method.

``````
public class Fibonacci {
public static void main(String[] args) {
System.out.println(0);
System.out.println(1);
//        printFibonacci(0, 1);
printFibonacciWithCondition(0, 1);
}

private static void printFibonacci(long penultimate, long previous) {
long current = penultimate + previous;
System.out.println(current);
printFibonacci(previous, current);
}

private static void printFibonacciWithCondition(long penultimate, long previous) {
long current = penultimate + previous;
if (current > Integer.MAX_VALUE) {
return;
}
System.out.println(current);
printFibonacciWithCondition(previous, current);
}
}
``````

After running the code, we see that the output ends with the number 1836311903. The number before this one is 1134903170. The sum of these numbers is 2_971_215_073, which is indeed greater than Integer.MAX_VALUE (2_147_483_647).

This change automatically fixed the long overflow bug. If you need to calculate more of the series, you will need to use other data types, such as BigInteger.

## Recursive descent and unwinding

Let's analyze step by step how our code is executed. To do this, we'll add an echo method and call it before and after the recursive call of the printFibonacciWithCondition method.

``````
public class Fibonacci {
public static void main(String[] args) {
System.out.println(0);
System.out.println(1);
printFibonacciWithCondition(0, 1);
}

private static void printFibonacciWithCondition(long penultimate, long previous) {
long current = penultimate + previous;
if (current > Integer.MAX_VALUE) {
return;
}
echo(true, penultimate, previous);
System.out.println(current);
printFibonacciWithCondition(previous, current);
echo(false, penultimate, previous);
}

private static void echo(boolean isBeforeRecursiveCall, long penultimate, long previous) {
if (isBeforeRecursiveCall) {
System.out.printf("Before method call with args: %d, %d. Current number = ", penultimate, previous);
} else {
System.out.printf("After method call with args: %d, %d\n", penultimate, previous);
}
}
}
``````

The program gives us this output:

0
1
Before method call with args: 0, 1. Current number = 1
Before method call with args: 1, 1. Current number = 2
Before method call with args: 1, 2. Current number = 3
Before method call with args: 2, 3. Current number = 5
Before method call with args: 3, 5. Current number = 8
Before method call with args: 5, 8. Current number = 13
Before method call with args: 8, 13. Current number = 21
Before method call with args: 13, 21. Current number = 34
Before method call with args: 21, 34. Current number = 55
Before method call with args: 34, 55. Current number = 89
Before method call with args: 55, 89. Current number = 144
Before method call with args: 89, 144. Current number = 233
Before method call with args: 144, 233. Current number = 377
Before method call with args: 233, 377. Current number = 610
Before method call with args: 377, 610. Current number = 987
Before method call with args: 610, 987. Current number = 1597
Before method call with args: 987, 1597. Current number = 2584
Before method call with args: 1597, 2584. Current number = 4181
Before method call with args: 2584, 4181. Current number = 6765
Before method call with args: 4181, 6765. Current number = 10946
Before method call with args: 6765, 10946. Current number = 17711
Before method call with args: 10946, 17711. Current number = 28657
Before method call with args: 17711, 28657. Current number = 46368
Before method call with args: 28657, 46368. Current number = 75025
Before method call with args: 46368, 75025. Current number = 121393
Before method call with args: 75025, 121393. Current number = 196418
Before method call with args: 121393, 196418. Current number = 317811
Before method call with args: 196418, 317811. Current number = 514229
Before method call with args: 317811, 514229. Current number = 832040
Before method call with args: 514229, 832040. Current number = 1346269
Before method call with args: 832040, 1346269. Current number = 2178309
Before method call with args: 1346269, 2178309. Current number = 3524578
Before method call with args: 2178309, 3524578. Current number = 5702887
Before method call with args: 3524578, 5702887. Current number = 9227465
Before method call with args: 5702887, 9227465. Current number = 14930352
Before method call with args: 9227465, 14930352. Current number = 24157817
Before method call with args: 14930352, 24157817. Current number = 39088169
Before method call with args: 24157817, 39088169. Current number = 63245986
Before method call with args: 39088169, 63245986. Current number = 102334155
Before method call with args: 63245986, 102334155. Current number = 165580141
Before method call with args: 102334155, 165580141. Current number = 267914296
Before method call with args: 165580141, 267914296. Current number = 433494437
Before method call with args: 267914296, 433494437. Current number = 701408733
Before method call with args: 433494437, 701408733. Current number = 1134903170
Before method call with args: 701408733, 1134903170. Current number = 1836311903
After method call with args: 701408733, 113490317
After method call with args: 433494437, 701408733
After method call with args: 267914296, 433494437
After method call with args: 165580141, 267914296
After method call with args: 102334155, 165580141
After method call with args: 63245986, 102334155
After method call with args: 39088169, 63245986
After method call with args: 24157817, 39088169
After method call with args: 14930352, 24157817
After method call with args: 9227465, 14930352
After method call with args: 5702887, 9227465
After method call with args: 3524578, 5702887
After method call with args: 2178309, 3524578
After method call with args: 1346269, 2178309
After method call with args: 832040, 1346269
After method call with args: 514229, 832040
After method call with args: 317811, 514229
After method call with args: 196418, 317811
After method call with args: 121393, 196418
After method call with args: 75025, 121393
After method call with args: 46368, 75025
After method call with args: 28657, 46368
After method call with args: 17711, 28657
After method call with args: 10946, 17711
After method call with args: 6765, 10946
After method call with args: 4181, 6765
After method call with args: 2584, 4181
After method call with args: 1597, 2584
After method call with args: 987, 1597
After method call with args: 610, 987
After method call with args: 377, 610
After method call with args: 233, 377
After method call with args: 144, 233
After method call with args: 89, 144
After method call with args: 55, 89
After method call with args: 34, 55
After method call with args: 21, 34
After method call with args: 13, 21
After method call with args: 8, 13
After method call with args: 5, 8
After method call with args: 3, 5
After method call with args: 2, 3
After method call with args: 1, 2
After method call with args: 1, 1
After method call with args: 0, 1

Here's a visualization of what is happening.

Let's say it again: the printFibonacciWithCondition method is called. It calculates the current number. If it suits us, then we display it and call the printFibonacciWithCondition method again with new arguments.

As long as the recursive method is being called, this is called "recursive descent". When recursive terminates and method calls return, we say that the call stack is "unwinding".

Recursion is an interesting topic in programming. To get a better handle on the material, let's change our task slightly. The new task is to output, in descending order, all numbers in the Fibonacci series that do not exceed Integer.MAX_VALUE. We've already written all the code needed for this task. All that remains is to swap the order of displaying the current number and calling the recursive method. That is, in the first example, the calculated number was displayed during the "descent", but now we need to "descend to the very bottom" and then display numbers "on the way back up". And of course, in the main method, we swap the two initial numbers of the sequence (zero and one) after display them after we call the recursive method. For readability, we omit the echo method.

``````
public class Fibonacci {
public static void main(String[] args) {
printFibonacciWithCondition(0, 1);
System.out.println(1);
System.out.println(0);
}

private static void printFibonacciWithCondition(long penultimate, long previous) {
long current = penultimate + previous;
if (current > Integer.MAX_VALUE) {
return;
}
printFibonacciWithCondition(previous, current);
System.out.println(current);
}
}
``````

The output will be:

1836311903
1134903170
701408733
433494437
267914296
165580141
102334155
63245986
39088169
24157817
14930352
9227465
5702887
3524578
2178309
1346269
832040
514229
317811
196418
121393
75025
46368
28657
17711
10946
6765
4181
2584
1597
987
610
377
233
144
89
55
34
21
13
8
5
3
2
1
1
0