# Recursion

Recursion means "defining a problem in terms of itself". This can be a very powerful tool in writing algorithms. Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves. For example, the Fibonacci sequence is defined as: F(i) = F(i-1) + F(i-2)

# Recursion

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself.

For example, we can define the operation "find your way home" as:

1. If you are at home, stop moving.

2. Take one step toward home.

3. "find your way home".

Here the solution to finding your way home is two steps (three steps). First, we don't go home if we are already home. Secondly, we do a very simple action that makes our situation simpler to solve. Finally, we redo the entire algorithm.

The above example is called tail recursion. This is where the very last statement is calling the recursive algorithm. Tail recursion can directly be translated into loops.

How would you write a recursive "algorithm" for finding Temple Square?

Another example of recursion would be finding the maximum value in a list of numbers. The maximum value in a list is either the first number or the biggest of the remaining numbers. Here is how we would write the pseudocode of the algorithm:

```        ```
Function find_max( list )

possible_max_1 = first value in list
possible_max_2 = find_max ( rest of the list );

if ( possible_max_1 > possible_max_2 )
else
end

end
```
```

## Parts of a Recursive Algorithm

All recursive algorithms must have the following:

1. Base Case (i.e., when to stop)

2. Work toward Base Case

3. Recursive Call (i.e., call ourselves)

The "work toward base case" is where we make the problem simpler. The recursive call, is where we use the same algorithm to solve a simpler version of the problem. The base case is the solution to the "simplest" possible problem (For example, the base case to adding a list of numbers would be if the list had only one number... thus the answer is the number).

## Simple Example: Add three numbers

Adding three numbers is equivalent to adding the first two numbers, and then adding these two numbers again.

## Matlab

```            ```
function result = add_numbers(a, b, c)

if      ( nargin() == 2 )
result = a + b;
else if ( nargin() == 3 )
result = add_numbers(a+b, c);
else
error('oops');
end

end
```
```

## Identify the 3 parts of the recursive algorithm:

All recursive algorithm must have the following three stages:

1. Base Case: if ( nargin() == 2 ) result = a + b;

2. "Work toward base case": a+b becomes the first parameter

This reduces the number of parameters to the function from 3 to 2, and 2 is the base case!

3. Recursive Call: add_numbers(a+b, c);

## Why Recursion Works

In a recursive algorithm, the computer "remembers" every previous state of the problem. This information is "held" by the computer on the "activation stack" (i.e., inside of each functions workspace).

Every function has its own workspace PER CALL of the function.

## Maze Example:

Consider a rectangle grid of rooms, where each room may or may not have doors on the North, South, East, and West sides.

How do you find your way out of a maze? Here is one possible "algorithm" for finding the answer:

For every door in the current room, if the door leads to the exit, take that door.

The "trick" here is of course, how do we know if the door leads to a room that leads to the exit? The answer is we don't but we can let the computer figure it out for us.

What is the recursive part about the above algorithm? Its the "door leads out of the maze". How do we know if a door leads out of the maze? We know because inside the next room (going through the door), we ask the same question, how do we get out of the maze?

What happens is the computer "remembers" all the "what ifs". What if I take the first door, what if I take the second door, what if I take the next door, etc. And for every possible door you can move through, the computer remembers those what ifs, and for every door after that, and after that, etc, until the end is found.

Here is a close to actual code implementation.

## Matlab

```            ```
% return true if we can find our way out
function success = find_way_out( maze, room )

for every door in the room

new_room = go_through_door( maze, door )

if  ( find_way_out ( maze, new_room ) )
take that door.
end
end

end
```
```

## Recursion can be equally well applied to computer algorithms:

Some Computer related examples include: Adding a list of numbers, Computing the Fibonacci sequence, computing a Factorial, and Sudoku.

1. ## Summing a list of numbers:

Question: What is a recursive solution to summing up a list of numbers? First you should note that the sum of [1 2 3 4 5 6 7 8 9]) is equal to 1 + sum of [2 3 4 5 6 7 8 9])!

2. ## Factorial

What is the definition of Factorial?

Answer: factorial(X) = X * (x-1) * (x-2) * ... * 2

Hmmm, but what does "(x-1) * (x-2) * ... * 2" equal?

What if we combine these definitions!

Answer 3: factorial(X) = X * factorial(X-1);

Lets write a recursive factorial function.

3. ## Fibonacci

What is the definition of the Fibonacci number at location X in the sequence?

Answer: fib(x) = fib(x-1) + fib(x-2);

This is a recursive definition.

Lets write a recursive function to compute the Nth number in the Fibonacci sequence.

4. ## Sorting

How can you sort a list of numbers using recursion?

Hint 1: Is it easier to sort a long list or a short list?

Hint 2: If you have two sorted lists, can you put them back together?

5. ## Sudoku

How would you use a computer solve a Sudoku? How about trying every possible combination of numbers? Note: this is a brute force approach. Here is one possible "algorithm":

Starting from the upper left "bucket" and moving across each row one column at a time (then down to the start of the next row, and so forth).

Hypothesize a valid number (what the heck, just try all 9 numbers) for the bucket. IF, you can solve the rest of the puzzle, BASED on the HYPOTHESIZED number, you have SOLVED the puzzle!

This is a recursive algorithm! Assume every box is assigned an index/label number (from 1 to 81):

Algorithm Overview Pseudocode:

```            ```

function solve_sudoku ( current_box_id )

if all the boxes are filled
return true; // solved!
end

// ignore already "filled" squares (assume they are correct!)
if the current box is filled
return the result of: solve_sudoku( next box );
end

// hypothesize all 9 possible numbers
for each possible number from 1 to 9
if that number is 'valid' (okay to put in box)  // test row,col,square
try that number in the box
if you can "solve_sudoku" for the rest of the puzzle
return true; // success!
end
end
end

return false; // failure

end
```
```

## Loops and Tail Recursion

Some recursive algorithms are very similar to loops. These algorithms are called "tail recursive" because the last statement in the algorithm is to "restart" the algorithm. Tail recursive algorithms can be directly translated into loops.