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
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)
That was a brief intro into recursion!
Resources
https://en.wikipedia.org/wiki/Call_stack?source=post_page-----5156e152a608----------------------
https://www.valentinog.com/blog/context/?source=post_page-----5156e152a608----------------------
https://www.geeksforgeeks.org/recursion/?source=post_page-----5156e152a608----------------------
Top comments (0)