# Recursion

**This tutorial covers:**

- Recursion and Examples
- Base Cases

**Before starting, you should be familiar with:**

- The BoGL basics
- Types
- Understanding Expressions
- Values
- Locally Defined Values
- Functions
- Conditional Expressions (If/Else)
- User Input
- Boards

**At the end, you should be able to:**

- Use recursion in any algorithm
- Illustrate how recursion works
- Explain what a base case is & it's importance

## What is Recursion?

Recursion is the act of a function making a call to itself. This technique is used to repeat computations.

Below is an example of what we would call a *recursive function*.

The function `recursiveFunction`

shown above is recursive because it has a call to itself within its defining expression `recursiveFunciton(x + 1)`

. This means that if it is called initially with an argument of `1`

, `recursiveFunction`

will make a call to `recursiveFunction`

with an argument of `2`

, which will then make a call to `recursiveFunction`

with an argument of `3`

, which will then make a call to `recursiveFunction`

with an argument of `4`

, and so on…

The function will repeatedy call itself like this and will not stop. **Excercise:**

- Try writing your own recursive function in the editor below.
- What happens when you call the function in the interpreter?

## The Base Case

To prevent a recursive function from recurring forever, you must add a *base case*. The base case is described as when the argument provided to the function **will not** trigger another recurrence, and the function will instead return without calling itself again.

Reaching the base case in a recursive function often means an end to the repetition.

Shown below is a recursive function that includes a base case.

The function shown above counts to 100, and will make 100 - x recursive function calls (assuming that x is less than 100). In this function, the argument of every recursive call is the argument of the last call plus one. The function will keep making these recursive calls until it reaches its base case, which is the argument being equal to or greater than 100.

Once a recursive call reaches the base case, the function will return a value to the last call, which then returns a value to the call before it and so on until a value is returned from the initial function call.

**Excercise:**

Write a function that takes an integer value as an argument, and makes an equivalent amount of recursive calls.

The initial call to the function is not a recursive call.

## Click to see a solution (but try yourself first!)

**Excercise:**

A factorial operation is denoted in math using the exclamation point after an integer. This operation means to multiply the number by every integer that is less than itself and greater than zero. Shown below are a few examples.

```
4! = 4 * 3 * 2 * 1 = 24
3! = 3 * 2 * 1 = 6
2! = 2 * 1 = 2
1! = 1
11! = 11 * 10 * ... * 2 * 1 = 39916800
x! = x * (x - 1) * (x - 2) ... * 2 * 1
```

The last example shown above is a generalized form of factorial, where x represents the integer whose factorial is being calculated.

Write the defining expression for a function that computes the factorial of an integer.

## Click to see a solution (but try yourself first!)

## Examples

Here are a couple of BoGL programs that utilize recursion.

**Example: Guess My Favorite Color**

Ever try to guess a friend's favorite color? Running the BoGL code shown in the example below will start a "Guess My Favorite Color" game. The argument `favoriteColor`

represents the color to be guessed. Calling the function `playGame`

(from the example below) will result in the user being repeatly asked for a color until the input matches the argument that was originally provided to `playGame`

.

In this example, recursion is used to repeatedly prompt the user for input until the correct input (which was the argument progided to the *playGame* function) is provided.

**Example: Find the Goose**

Imagine we would like to find the location of the first goose in a line of 5 birds.

Spot in line | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

Bird | Duck | Duck | Duck | Goose | Duck |

The `findGoose`

function shown below will check each spot in a line of birds (starting at the spot given as argument) until it finds a spot that holds a goose.

In this example, recursion is used to iterate through the line of birds until the first goose is encountered.