In this lesson, we will learn about how to set up and execute a recursive function in Swift.

Recursion: Swift

In the last exercise, you created a condition that determines whether or not `findFactorialRecursively()` calls itself. We call this `if` block the _recursive case_.

In recursion, the recursive case is the condition under which a function calls itself. We call this the recursive case because, recursion is defined as a process that includes a function calling itself. 

At this point, we are still missing a couple of components from our recursive method:

1. 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.

2. `findFactorialRecursively()` always returns `0` – the value set to `recursiveSolution` (see **Factorial.swift** to the right) is zero, because we always return `0` after the `if` block in `findFactorialRecursively()`.

We'll tackle **#1** next. 

The Recursive Case

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.

Take a look at the `**Factorial.swift**` file to the right where we have the beginning of a recursive implementation of a factorial. 

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

If you run the code now, you'll see the following output: 

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

The function isn't returning the correct answer at the moment (factorial of 4 is not 0, it's ) but it will! In this lesson, we'll walk you through correcting the function and teach you about the intricacies of recursive functions, what a base case and recursive case are, and more. Let's get started!


What is Recursion?

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 function that returns the _factorial_ of a number. An integer’s factorial is the product of an integer and all the positive numbers less than it.

Let’s consider 4 factorial denoted by `4!`:

`4! = 4 × 3 × 2 × 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.

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

Before we dive into recursion, let’s consider how a factorial is implemented with an iterative approach.

Introduction to Recursion in Swift

Despite returning a call to `n * findFactorialRecursively(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 Swift creates for:

```
return n * findFactorialRecursively(of: n - 1)
```

Swift would create a call stack with the following events:

1. `findFactorialRecursively(of: 3)` = `3 * findFactorialRecursively(of: 2)`
2. `findFactorialRecursively(of: 2)` = `2 * findFactorialRecursively(of: 1)`
3. `findFactorialRecursively(of: 1)` = `1 * findFactorialRecursively(of: 0)`

The return value associated with each function call depends on the value returned by `n - 1`. Do you remember what our function 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 other than zero.

The Base Case

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.swift**, we included both the iterative and recursive solutions to factorial. As you learn more about recursion, you may find the 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.