# 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!

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?