# Recursion

1. If you are at home, stop moving.
2. Take one step toward home.
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

1. Base Case (i.e., when to stop)
2. Work toward Base Case
3. Recursive Call (i.e., call ourselves)

# Matlab

function result = add_numbers(a, b, c)

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

end

# Identify the 3 parts of the recursive algorithm:

1. Base Case: if ( nargin() == 2 ) result = a + b;
2. “Work toward base case”: a+b becomes the first parameter
3. This reduces the number of parameters (nargin) sent in to the function from 3 to 2, and 2 is the base case!

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

return true
end

end

% there were no ways out :(
return false

end
function success = find_way_out( maze, room )

if room is exit → return true

room ← mark as visited

% rest of code
...

end
function success = find_way_out( maze, room )

% exit chack

if room is visited → return false

% rest of code
...

end

# Recursion can be equally well applied to computer algorithms:

• Summing a list of numbers:
1. 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])!
• Factorial
1. What is the definition of Factorial?
2. Answer: factorial(X) = X * (x-1) * (x-2) * … * 2
3. Hmmm, but what does “(x-1) * (x-2) * … * 2” equal?
5. What if we combine these definitions!
6. Answer 3: factorial(X) = X * factorial(X-1);
7. Lets write a recursive factorial function.
• Fibonacci
1. What is the definition of the Fibonacci number at location X in the sequence?
2. Answer: fib(x) = fib(x-1) + fib(x-2);
3. This is a recursive definition.
4. Lets write a recursive function to compute the Nth number in the Fibonacci sequence.
• Sorting
1. How can you sort a list of numbers using recursion?
2. Hint 1: Is it easier to sort a long list or a short list?
3. Hint 2: If you have two sorted lists, can you put them back together?
• Sudoku
1. 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”:
2. 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).
3. 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!
4. This is a recursive algorithm! Assume every box is assigned an index/label number (from 1 to 81):
5. 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

--

--

--

## More from Rami Louhibi

Love podcasts or audiobooks? Learn on the go with our new app.