Summer’s over — what’s your move? Join Pro for 50% off using code [MAKEITHAPPEN](https://www.codecademy.com/checkout?periods=year&plan_id=proGoldAnnualV2&discountCode=MAKEITHAPPEN)


In this lesson, you will learn how to implement a recursive function in Java.

Recursion in Java

Throughout this lesson, you learned about recursion as you coded a factorial method. While every recursive problem is a little different, the following features will always be required:
- *Recursive case* – the conditions under which the method will perform an action and call itself.
- *Base case* – the conditions under which the method returns a value without making any additional calls to itself.

In this example, we started by considering the recursive case. With some problems it may be easier to start with the base case. Regardless, when you are dealing with a recursive problem, start by thinking about potential recursive and base cases for your solution.

In **Factorial.java**, to the right, we included both the iterative and recursive solutions to factorial. Both approaches work equally well for this problem. 

As you learn more about recursion, you may find recursive syntax to be more readable and easier to understand when addressing certain problems. Consider it another tool in your toolbox as you approach increasingly challenging programming problems.


Review

Recursion is a powerful tool for solving problems that require the execution of an action multiple times until a condition is met. For many problems, a recursive solution will result in fewer lines of code and will be easier to comprehend than a solution that uses a `for` or `while` loop. 

You may find that recursion is a difficult concept to wrap your head around at first. That's fine! This lesson is meant as an introduction. As you see more examples and get more practice, you will start to feel comfortable with the concept.

In this lesson, you will learn to implement a recursive method that returns the _factorial_ of a number. An integer's _factorial_ is the product of an integer and all positive numbers less than it.

Let's consider `4` factorial:

```tex
4! = 4 \times 3 \times 2 \times 1 = 24
```

Four factorial is equal to the product of `4 x 3 x 2 x 1`, which is `24`. The exclamation mark denotes that the number `4` is being factorialized.

`1!` and `0!` are both valid base cases of factorial. The factorial product of both numbers is 1.

Before we dive into recursion, you will consider how factorial is implemented with an *iterative* approach. 


Introduction

Despite returning a call to `n * recursiveFacorial(n - 1)`, the solution to the last exercise did not change the output:

```
Execution context: 4
Execution context: 3
Execution context: 2
Execution context: 1
0
```

_Why is the returned value not equal to the product of `n` in each execution context?_ The short answer: we didn't define a *base case*. To understand the need for a base case, it's worth discussing the call stack that Java creates when you call `recursiveFactorial()`.

If you were to call:

```java
recursiveSolution = recursiveFactorial(3)
```

Java would create a call stack with the following events:
1. `recursiveFactorial(3)` = `3 * recursiveFactorial(2)`
2. `recursiveFactorial(2)` = `2 * recursiveFactorial(1)`
3. `recursiveFactorial(1)` = `1 * recursiveFactorial(0)`

The return value associated with each method call depends on the value returned by the `n - 1` context. Do you remember what our method returns when `n` is equal to `0`? 

Because our current implementation returns `0` when `n` is zero, each product in the above call-stack, starting with event 3, will be multiplied by `0`. This leads to a `0` solution for each of the contexts above it.

We can fix this with a *base case*. When the base case is met (`n == 0`), the factorial method should return a number. Hint: the number should not be zero.


Base Case

So, what is recursion? 

*Recursion* is a computational approach where a method calls itself from within its body. Programmers use recursion when they need to perform the same action multiple times in a row until it reaches a predefined stopping point, also known as a _base case_.

Let's think about this in the context of our factorial example. Below is the beginnings of a recursive implementation of factorial. This code is in **Factorial.java**, to the right.

```java
...
public static int recursiveFactorial(int n) {
    if ("SOME CONDITION") {
        System.out.println("Execution context " + n);

        recursiveFactorial(n - 1);
    }

    return 0;
}
...
```

Within the `recursiveFactorial()` method, we check whether a condition is met. If it is, then we print the value of `n` and return a call to `recursiveFactorial(n - 1)`. If the condition is not met, we return `0`.

Can you think of a condition that will result in the following response when we call `recursiveFactorial(4)`?

```
Execution context: 4
Execution context: 3
Execution context: 2
Execution context: 1
0
```

We want a condition that stops being true after `n` is less than `1`, so the correct answer is `n > 0` or `n >= 1`. At this point, we have the beginnings of a recursive method, but we're still not returning anything meaningful. 


Recursion

In the last exercise, you created a condition (`n > 0` or `n >= 1`). This condition is important, because it defines whether or not `recursiveFactorial()` calls itself. We call this `if` block the *recursive case*.

In recursion, the *recursive case* is the condition under which a method calls itself. We call this the recursive case because, as mentioned in the last exercise, recursion is defined as: a process that includes a method calling itself.

At the end of last exercise, your output should have looked like:

```
Execution context: 4
Execution context: 3
Execution context: 2
Execution context: 1
0
```

At this point, we are still missing a couple of components from our recursive method:
- Calculating the product of each number – while the current implementation does access all the numbers that we need to multiply, we do not calculate their product.
- `recursiveFactorial()` always returns `0` – the value set to `recursiveSolution` (see **Factorial.java** to the right) is zero, because we always return `0` after the `if` block in `recursiveFactorial()`.
