To understand recursion you must first understand recursion
Hopefully this joke makes sense by the end of this!
Before we dive into recursion let’s go over some concepts that you’ll need.
When a function is called an execution context is placed on 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.
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.
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)
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.
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.
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)
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)
That was a brief intro into recursion!