# Chapter 8: Recursion

This chapter discusses recursion, or recursive loops. **Recursive loops** are a loop structure in which a method invokes itself until a certain condition is met. In other words, a method will call itself repeatedly to create a loop.

Here is the basic layout of a recursive method.

## Recursive Counter With Static Variable

The first step to create a recursive loop is to create a method that does something we want to repeat. The method in this example will print out the numbers one through five to the screen. Then the loop will end. I have opted to call this method recursivePrinter()

In order to keep track of what iteration of the loop we are on, I have opted to declare a variable outside of the method, so it doesn't get re-initialized every time the loop executes. We also don't want to declare it within the main method, because if we did that, the variable would only be accessible by the main method. In this case, I have declared `static int i = 1;`

outside the main method, but still within the class of the file. Here, it must be declared using the keyword static to show that it is a single entity accessible to all the methods in the class.

```
public class Main {
static int i = 1;
public static void main(String[] args) {
recursivePrinter();
}
static void recursivePrinter(){
System.out.print(i);
i++;
if(i<6){
recursivePrinter();
}
}
}
```

Look at the recursivePrinter() method. This method prints out the current value of i, increments i by 1, and then, if i is less than 6, calls itself again. Once i is no longer less than 6, the method will no longer call itself, and the program will end.

12345

Here is a step-by-step breakdown of exactly what's happening if you need further clarification:

- A static variable is declared at the class level, so it can be used by all methods in that class.
- The main method calls the recursivePrinter method.
- The recursivePrinter method prints 1, the value of i, increases it by 1, so i is now 2, and then checks if i is less than 6. Since 2 is less than 6, it calls recursivePrinter again.
- When recursivePrinter is called a second time, i now has a value of 2. It prints out 2, increases i to 3, checks the value, and calls itself again.
- It does this again and again for i=3, i=4, and i=5.
- On the last time, i=5, it increments the value by 1 to 6. Since 6 is not less than 6, the recursivePrinter method does not get called again, and the loop is done executing.

## Recursive Counter With Parameter

Now we're going to take a look at another way we could create a recursive counter that prints out the numbers 1 through 5, without the use of a static variable. Instead, we will keep track of the current iteration of the loop by passing the variable back to the method itself as an argument.

```
public class Main {
public static void main(String[] args) {
recursivePrinter(1);
}
static void recursivePrinter(int i){
System.out.print(i);
i++;
if (i<6){
recursivePrinter(i);
}
}
}
```

12345

**Step by step breakdown:**

- The main method calls recursivePrinter, passing 1 as an argument.
- recursivePrinter prints out i, which is now 1, increments i by 1, and then calls itself, passing the number 2 as an argument.
- recursivePrinter prints out i, which is now 2, increments i by 1, and then calls itself, passing the number 3 as an argument, and so on.
- When i = 6, the method stops calling itself because of the condition we set and the program is done executing.

### Memory Concept

Every time the recursive method calls itself, a new int i is declared and loaded into memory, as part of the method declaration where we set the parameter `(int i)`

. This may lead to a performance *decrease* as a new variable called "i" is being initialized every time the loop runs. This is different from the previous example, where i was declared as a static class-level variable.

## Recursion With Returns

Since it is possible to return a method, we can also recursively return the method itself. This is another way to make a recursive loop. Recall that a factorial is a whole number, multiplied by every whole number coming before it. Look at the following example, which finds the factorial using recursive return statements.

```
public class Main {
public static void main(String[] args) {
System.out.println("5 factorial is: " + getFactorial(5));
}
static int getFactorial(int x){
if(x!=1){
return x * getFactorial(x-1);
}
else{
return 1;
}
}
}
```

5 factorial is: 120

Note that we used a return of 1 when x=1, this is what ultimately ends this recursive loop. Here is a step-by-step explanation.

- The main method calls the getFactorial method, x is equal to 5.
- The getFactorial method needs to return 5*getFactorial(4), so it must now figure out what getFactorial(4) is
- getFactorial(4) is 4*getFactorial(3), so it must now figure out what getFactorial(3)is
- getFactorial(3) is 3*getFactorial(2), it must now figure out what getFactorial(2) is
- getFactorial(2) is 2*getFactorial(1), and getFactorial(1) returns a value of 1.
- The program now knows getFactorial(1) is 1, so it can figure out getFactorial(2)
- The program knows that getFactorial(2) is 2*1=2, so it can now figure out what getFactorial(3) is
- The program knows getFactorial(3) is 3*2=6, so it can now figure out what getFactorial(4) is
- The program knows getFactorial(4) is 4*6=24, so it can now figure out what getFactorial(5) is
- The program knows getFactorial(5) is 5*24=120, so it returns this at the end.

In a way, it works down to 1, and then back up.

## Performance Impact

Let's look at how you can measure the performance of some code in Java. The easiest way to do this is to measure the time elapsed from when the code begins to execute to when the code is done executing. For this exercise, we'll be looking at time measured in nanoseconds. Note that this is not the most scientific way to measure performance time, but for our demonstration purposes, will suffice.

The format for measuring elapsed time in ns looks like this:

Measure Elapsed Time in ns```
long startTime = System.nanoTime();
//code to test execution time of here
long endTime = System.nanoTime();
long timeElapsed = endTime - startTime;
System.out.println("That took: " + timeElapsed + " ns");
```

We're going to be comparing the time it takes to execute a factorial calculation of 100, using two different methods. First, let's calculate 100 factorial and see how long it takes using the code from the last chapter, done with a for loop:

Measuring Performance of For Loop```
public class Main {
public static void main(String[] args) {
long startTime = System.nanoTime();
double answer=getFactorial(100);
long endTime = System.nanoTime();
long timeElapsed = endTime - startTime;
System.out.println("That took: " + timeElapsed + " ns");
System.out.println("100 factorial is: " + answer);
}
static double getFactorial(double x){
//the running factorial result
double result = 1.0;
//iterate from 1 through x, incrementing loop by 1 each time
for(int i = 1; i <= x; i++){
//multiply the result by i, the next number in the sequence
result = result * i;
}
return result;
}
}
```

That took: 2700 ns 100 factorial is: 9.33262154439441E157

Note that time time it takes may depend on how fast your CPU is, what else it's doing in the background, and several other extraneous factors. After running the code ten times, I got values of: 2700, 3600, 2600, 2500, 2400, 2600, 2600, 2600, 3300, 2400. As you can see, there was quite a bit of range in time, but it all hovered between 2400 and 3600ns. The average of these values is: 2730ns on my machine.

Next, I'm going to modify the previous recursive example of getFactorial to work with doubles instead of ints, calculate getFactorial(100) ten times recursively, and measure the amount of time it takes every time.

Measuring Performance of Recursive Loop```
public class Main {
public static void main(String[] args) {
long startTime = System.nanoTime();
double answer=getFactorial(100);
long endTime = System.nanoTime();
long timeElapsed = endTime - startTime;
System.out.println("That took: " + timeElapsed + " ns");
System.out.println("100 factorial is: " + answer);
}
static double getFactorial(double x){
if(x!=1){
return x * getFactorial(x-1);
}
else{
return 1;
}
}
}
```

That took: 3900 ns 100 factorial is: 9.33262154439441E157

After executing the program 10 times with the recursive method, I measured elapsed times of: 3900, 3200, 3400, 3600, 3400, 4200, 3300, 3500, 3600, and 4100ns. The average is 3620ns, considerably higher than the 2730ns average when I used a for loop to calculate the factorial. It's an increase in time of nearly 33%. So it's 33% slower to recursively find the factorial than it was to do it using a for loop.

While this may not seem like a big deal when measuring in nanoseconds, imagine if the scale was much larger. If we could do something recursively that took an hour, but it only took 44 minutes doing it another, more optimized way, we should go with the more optimized version. The time gains are significant, and this doesn't even consider the additional RAM needed to calculate this recursively. Remember, Java had to load each getFactorial() method into system memory each time it went through the loop, and then wait for each method to return something. This means at one point, Java had 100 methods loaded into memory, waiting for it to finally return 1 at the end, before it could go back and finish closing each method individually. At scale, such wasteful methods could cause the program to run out of memory and crash.

The primary goal of this chapter was to show you what recursion is and how it works. It is a fundamental Computer Science topic. Other than for simple programs, or to prove that you understand the concept to an instructor, I do not recommend you use recursive code in Java. It can bog down memory and impact overall program performance. Be aware that it exists, in case you come across it in your studies, but avoid using it when possible. Java is not optimized for recursion. You're usually better off using a standard loop structure, such as the ones discussed in the previous chapter.

## Assignment 8: Fibonacci Sequence

**Instructions: ** The Fibonacci sequence is a series of numbers in which each number is the sum of the two previous numbers. For example, the first 10 numbers in the Fibonacci sequence look like this:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Your goal is to create a recursive method that returns the sum of the previous two numbers. For example, fibonacci(5) returns the 5th term in the sequence.

Here is some code to start with. What code goes in the recursive method?

```
public static void main(String[] args){
//Call the Fibonacci method for the first 25 terms
for(int i = 1; i<=25; i++){
System.out.print(fibonacci(i) + ", ");
}
}
//The recursive Fibonnaci method
public static int fibonacci(int term) {
//Your Code Here
}
```

**Hints: **

- The first two numbers will always be 1. So for
`num==1`

and`num==2`

the recursive method should always return 1. - For each term in the sequence greater than 2, it should return the sum of the previous two numbers by calling itself recursively.

The program should output this if done correctly:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025,

Here is the solution for the entire program:

```
public class CalcFib {
public static void main(String[] args){
//Call the Fibonacci method for the first 25 terms
for(int i = 1; i<=25; i++){
System.out.print(fibonacci(i) + ", ");
}
}
//The recursive Fibonnaci method
public static int fibonacci(int term) {
//if we are on the first or second number in the sequence, return 1
if (term == 1 || term == 2){
return 1;
}
//otherwise return the sum of the previous two numbers in the sequence
return fibonacci(term - 1) + fibonacci(term - 2);
}
}
```