Recursive solution for rspec3 [stringify(base)]

I’d love some help understanding how recursion works, especially in the context of that problem which was really difficult to wrap my head around.

I was able to work out the iterative solution, but am intrigued by recursion/how to do it/when to do it/etc.

Thanks! :slightly_smiling_face:

Hey Laurette,

The concept of recursion refers to a method that calls itself. Let’s take a look at an extremely basic recursive function.

def countdown(n)
   if n <= 0
      puts "Blastoff!"
   else 
      puts n
      countdown(n - 1)
   end
end

In the above example, we define a method, countdown, which will either print “Blastoff”, or print the input number and then make a recursive call to our method with n decremented by one. If we call countdown(0), the method will simply output "Blastoff!". Alternatively, countdown(1) will first output 1 and then execute countdown(n-1), i.e. countdown(0). This pattern continues, so if we make, say, a call to countdown(8) will result in:

#  8
#  7
#  6
#  5
#  4
#  3
#  2
#  1
#  Blastoff!

The important thing to note here is that we have a base case–a condition in which we stop executing our code (n == 0)–and an inductive step–something that brings us closer to our base case (n - 1). Without these two pieces, our code would execute forever.

If we think about these two pieces–a base case and inductive step–in the context of recursive stringify, we can see a similar structure. Consider the recursive solution:

def stringify(base)
    return "0" if self == 0

    low_digit = self % base
    leftover = self - low_digit

    digits = [
      "0", "1", "2", "3", "4", "5", "6", "7",
      "8", "9", "a", "b", "c", "d", "e", "f"
    ]

    if leftover > 0
      (leftover / base).stringify(base) + digits[low_digit]
    else
      digits[low_digit]
    end
end

We hit our base when either self or leftover are zero. Our inductive step happens when we calculate the leftover, divide it by our base, and then call stringify on the result.

Let’s say we called 35.stringify(10):

We first skip our return, and calculate the low_digit, 5. We’ll hold onto that.

We then find what’s leftover, 30.

Then, in our if statement, we make a recursive call on (leftover / base), and take whatever that returns and add it to "5". If we stepped through our recursive call, we would see that this time, we would hit our base case, and eventually return "3".

Recursion is great for problems that need to do the same thing over and over again. Hope this clears things up!

  • David
1 Like

It absolutely does! Do you know of any other good resources for learning more about it?