Recursion
DBC Week 8: Challenge #7
June 19, 2015
In programming recursion is a process where a function calls itself within a block. I like to think of it as what that last line really says; a method that uses recursion is a method where that method re -occurs. Why are all the topics that I choose to blog about so cyclical in their explanation?
As a matter of fact, just to keep in the theme of cyclical, you can think about a recursive function being just like a loop.
Recursion can be used in a problem when a repeating pattern is recognizable. The easiest way to show you how this works is to show it working through an example and a story. So here goes. Imgine this:
"99 Bottles of Beer". Heard of it? C'mon sure ya have. Who hasn't? Well turns out you are traveling the world, and presently find yourself making ends meet by tending bar in an out of the way Tiki Shack in some country who's name you can't pronounce. You've been indulging in too many refreshing libations with your crowd when you discover no one there has ever once chanced across a drunken uncle in a lawn chair singing this song. They all think it sounds like a great song, and should sing it, but they need the lyrics. You could just tell them the lyrics since they repeat easily enough, but considering the tilt of the room and the swagger of the patrons, you decide that it will be best to have some sheet music to refer to.
You tear a page out of your travel journal and start writing. "99 bottles of beer on the wall, 99 bottles of beer! Take one down, pass it around, 98 bottles of beer on the wall!"
Quickly you realize that no one is going to be left standing in the establishment by the time you are get the whole song down. You need to figure out how to get these lyrics down on paper quickly, the crowd is brimming with anticipation. Looking back down on your paper it dawns on you that the nearly the entire song is comprosed of those two sentences you just wrote. If you could only figure out how to automate the number of beers decreasing by 1, you could write a program to print out all the lyrics with all the correct bottle numbers, until there are no more bottles on the wall.
You clear a spot on the bar, open up your laptop, and get to work on a Ruby script. First you start with a method definition:
def beer_bottles(num)
return "No more bottles of beer on the wall!" if num <= 0
puts "#{num} bottles of beers on the wall!, #{num} bottles of beer!"
puts "take one down, pass it around,"
puts "#{num - 1 } bottles of beer on the wall!"
end
Thankfully you realized that by being passing the method an argument you can control how long the song is going to last. You could call it "5 Bottles of Beer on the Wall" if you wanted.
You look it over, feel pretty slick, and call the method:
beer_bottles(99)
But all that prints out is:
99 bottles of beers on the wall!, 99 bottles of
beer! take one down, pass it around, 98 bottles of beer on the wall!
The code is not counting down! It stopped after 98, it's supposed to go to 0. You forgot the recursive part, the part that repeats itself until the goal is met! Unless the function 'beer_bottles' actually calls 'beer_bottles' inside itself, the lyrics are not going to print out past 1 minus the number you give it. You go back to the keyboard and add one line to your script:
def beer_bottles(num)
return "No more bottles of beer on the wall!" if num <= 0
puts "#{num} bottles of beers on the wall!, #{num} bottles of beer!"
puts "take one down, pass it around,"
puts "#{num - 1 } bottles of beer on the wall!"
beer_bottles(num-1)
end
The shouts and hecklings from the crowd grow louder as you change it from 99 bottles to 3, just to make sure it works and run the code:
3 bottles of beers on the wall!, 3 bottles of
beer! Take one down, pass it around, 2 bottles of beer on the wall!
2 bottles of beers on the wall!, 2 bottles of beer! Take one down,
pass it around, 1 bottles of beer on the wall!
1 bottles of beers on the wall!, 1 bottles of beer! Take one down,
pass it around, 0 bottles of beer on the wall!
You change the call back to 'beer_bottles(99)'' and run the code for the crowd. Someone looks over your shoulder sees the screen and soon thereafter the bar patrons are raccously belting out the tune. Good job! You just used recursion.
This is a very basic and simple idea of how recursion works, but I hope this made it easy to understand. If you are looking for more examples of how recursion works without getting this silly song stuck in your head try checking out one of the countless examples of how to build a method to find the factorial of a number.This one draws it out very well:
Or check out this video by Joshua Creek which walks you through buildingexamples in code:
Thanks for taking the time to read this. Email me any questions or comments.