recursion.md

Recursion

You know functions are a powerful way to write code once and use it many different times. Parameters make functions more useful by allowing for simple changes each time. Recursion builds on this to make functions even more powerful.

A recursive function is a function that calls itself with a different parameter. If it calls itself forever, the program will never end, so we need a "base case" to tell it when to stop.

That's all there is to it, but it is tricky to master.

Factorial Example

When is recursion useful? Any time there is a problem that can be broken down into smaller identical sub-problems.

For example factorial in math, written 5! This is 5x4x3x2x1. Do you see that 5!=5x4! ? When should we tell the program to stop?

Here is an implementation, click here to visualize it step by step.

def factorial(num):
  if num == 1:
    return 1
  return num * factorial(num-1)
	    
value = factorial(5)
print(value)

Try These

Here are three more math problems:

• Powers
• Triangle numbers
• Fibonacci numbers

The CodingBat website is asking for Java code, so instead write your code in your regular Python environment (you don't need the CodingBat website to tell you if it is correct).

Printing Recursively

Those examples were returning numbers. What if you just want to print?

def print_by_letter(string):
  print(string[0])
  if len(string) > 1:
    print_by_letter(string[1:]) #substring from 1 spot to end
  
print_by_letter("hello")

Notice this example also handles the base case differently, which is possible since no value is returned. In order to stop, it just doesn't make another recursive call.

This is something that can be solved either by standard loops or with recursion. Often simple practice problems can be solved either way, but will ask you to do it recursively for practice.

Can you write recursive functions to print the hailstone sequence and juggler sequence?

Fractals

Graphics + recursion = fractals

Check out this example that is only recursive in the x direction

How does it know when to stop? Can you make a different fractal for the x direction?

Let's make the jump to two dimensional fractals. It can be hard to achieve a desired fractal, however there are many cool things you can make just by experimenting. Here is one that is colorful.

Here is a good one to try (finished code):

Can you draw the square in the middle and make 8 recursive calls? Can you use size for the base case instead of manually counting the depth? Hint: it can be difficult to jump to a perfect resursive call each time. I sometimes like to manually calculate the locations for the next level, which helps me see the math equation for the recursive call.

Tree fractals with lines can be made when using a helper function to calculate x, y based on angle, length. Here is a starter file.

Here is another classic one (you can use triangles or lines):

Towers of Hanoi

This is a recursive solution that seems pretty magical. It would be very hard to solve with loops, and it isn't intuitive the order of steps necessary, but a few lines of recursive code solves it with ease.

    Our goal is to move the entire tower to the middle peg.
    We can only move one disk at a time.
    We can never place a larger disk on a smaller one. 

Try solving it manually here with 4 or 5 discs (note that the goal on that website is to move everything to the third peg).

It is trivial with 2 discs: move the 0 (smallest) disc to the spare column, move the 1 (largest) disc to the destination column, move the 0 disc to the destination column. The same pattern holds with more discs: move the whole stack above the largest to the spare column, move the largest to the destination column, move the whole stack you just moved to the spare column to the destination column. See the visual

Here is some recursive psuedo-code:

FUNCTION MoveTower(disk, source, dest, spare):
IF disk == 0, THEN:
    move disk from source to dest
ELSE:
    MoveTower(disk - 1, source, spare, dest)
    move disk from source to dest
    MoveTower(disk - 1, spare, dest, source)

Go here to step through that recursive algorithm for 5 discs. Pretty impressive! That same algorithm can solve it for any size, as long as there is enough time.

Here is starter code for you to do your own implementation (and peek at the finished version if needed). It is a perfect use case for the provided Stack data structure, pushing and popping elements.

This shows the magic of recursion: imagine solving this with loops somehow. Also mind blowing - where is the rule "we can never place a larger disk on a smaller one" programmed?