Recursion

To understand recursion you must first understand recursion

Hopefully this joke makes sense by the end of this!

A bit of background

Before we dive into recursion let’s go over some concepts that you’ll need.

What happens when you call a function?

When a function is called an execution context is placed on the call stack.

What is the call stack?

The call stack is a pretty deep topic but for our purposes just know that it keeps track of what function is being executed.

What is an execution context?

Don’t worry about it. Just know that when you call a function you are putting instructions, variables, and parameters onto for that function call onto the call stack.

What is a Stack?

A stack is a data structure that follows the first in last out procedure. Imagine, that you have a stack of plates. You can place one plate on top of the other and to remove a plate there must be no plates on top of it. With that in mind we know that the first plate we put down will be the last one we get we get out because we have to remove the plates on top of it first.

# Ruby
def speak
  sayWords
end
def sayWords
  return "Hello there"
end
puts speak
#output --> "Hello there"

#Call Stack
#1. sayWords --> Speak calls sayWords so that gets placed on the stack as #well
#0. speak --> Our program begins by calling speak so it gets placed on #the stack

The thing to note is that we call speak which calls sayWords but speak doesn't finish until sayWords finishes.

Recursion is the repeated application of a procedure. In software we see this concept in recursive functions.

A recursive function is a function that calls itself…Let's play with that idea.

# Ruby 
def addUp
  addUp
end
#output --> Stack Overflow Error

We get an error here because the function is endlessly calling itself creating an infinite loop. This loop continues until the call stack is full and throws you a stack overflow error.

At this point this idea seems pretty useless. Buts lets say we add a condition or a base case to this behavior.

# Ruby 

def count_down(num)
  if num == 0
    return
  else
    puts num
    count_down(num - 1)
  end
end
count_down(3)

#output 
#--> 3
#--> 2
#--> 1
#Call Stack
#3. count_down(0)
#2. count_down(1)
#1. count_down(2)
#0. count_down(3)
#What's going on
#Call to count_down(3)
#puts 3 

# Note that count_down(3) still isn't done because its waiting for #count_down(2) 
#Call to count_down(2)
#puts 2
#Call to count_down(1)
#puts 1
#Call to count_down(0)
#Base Case Hit
#return to count_down(0)
#count_down(0) execution complete
#count_down(1) execution complete
#count_down(2) execution complete
#count_down(3) execution complete
#COMPLETE!

Let’s do the same without recursion.

# Ruby 

def count_down(num)
  while num != 0
    puts num
    num -= 1
  end
end
count_down(3)

#output 
#--> 3
#--> 2
#--> 1
#Call Stack
#0. count_down(3)

Why should you use recursion?

You probably shouldn’t. In most situations you can accomplish the same with a loop. Also, since recursion leverages the call stack the program could run into a stack overflow error.

However recursive solutions can be more elegant to read. It’s said that recursive solutions divide and conquer the problem by turning a large problem into a series of smaller ones. Let’s take a look at an example.

Example

The function we want to write takes in two numbers, multiplies them, and returns the value. The catch is that you can’t use the * operator.

So our large problem is multiplication and we will use a series of additions to solve it.

Regular Function

def multiply(num1, num2)
  result = 0
  num1.times do
    result += num2
  end
  return result
end
multiply(5, 4)

#output --> 20
#Call Stack 
#0. multiply(5, 4)

Recursive Function

def multiply(num1, num2)
  if num1 == 0
    return 0
  else 
    return (num2 + multiply(num1 - 1, num2))
  end
end
multiply(3, 2)
#output --> 30

#Call Stack
#3. 2 + multiply(0, 2)
#2. 2 + multiply(1, 2)
#1. 2 + multiply(2, 2)
#0. multiply(3, 2)
#What's going on
#Call to multiply(3, 2)
#Call to 2 + multiply(2, 2)
#Call to 2 + multiply(1, 2)
#Call to 2 + multiply(0, 2)
#Base Case Hit
#0 returned to 2 + multiply(0, 2) --> 2 + 0
#2 returned to 2 + multiply(1, 2) --> 2 + 2
#4 returned to 2 + multiply(2, 2) --> 4 + 2
#6 returned to multiply(3, 2)