#19 - But All My Friends Have Trampolines

Lets step away from Kotlin for a minute and revisit Groovy. Let's also revisit an alternate solution to the looping problem, recursion. To really demonstrate this feature, I am going to need to show you two solutions. First the recursive Groovy solution.

def fb
fb = {i, s = "" ->
    s = ((i%3)
        ? ((i%5)?i:"Buzz")
        : (i%5?"Fizz":"FizzBuzz")) + "\n" + s
    i <= 1 ? s : fb(i - 1, s)
}

fb(100)

This is a very simple recursive solution.  Base case happens on line 6 if i is one or less. Lines 3-6 determines the fizzy and buzziness, and line 9 sets the limit with the first call in. It works, trust me. In fact, try it out! You can download Groovy if you don't already have it, or you can Etry it out online.

Really. Go try it. Right now. I'll wait. It's important. No, seriously. Do it.

Tried it already? Great, now go change line 7 so that it will calculate FizzBuzz from one to one thousand. Did it work? Great let's move on. Wait, what? It didn't work? Something about a StackOverflowError? Awesome, you did it right. Let's continue the discussion.

The principal problem with deeply recursive solutions is the sheer amount of bookkeeping needed to keep the recursion straight.  Since this is a deep rather than a broad recursion each and every step in the iteration takes up space on the stack.  Each iterative step costs memory, and memory is limited unlike clock cycles.

So how do we fix this? Install a trampoline, invite the neighbor kids over, and see who you can chain-bounce onto the roof.

def fb
fb = {i, s = "" ->
    s = ((i%3)
        ? ((i%5)?i:"Buzz")
        : (i%5?"Fizz":"FizzBuzz")) + "\n" + s
    i <= 1 ? s : fb.trampoline(i - 1, s)
}.trampoline()

fb(100)

This is the actual solution for this week.  With the simple addition of two calls to the trampoline method in lines 6 and 7 this recursive solution now uses a form of a technique called tail recursion, where instead of layering on another level of memory for the stack we take the existing layer wipe it clean, and just jump back to the beginning of the method without a subroutine. What was once a gosub is now a goto. And we are no no longer beholden to the size of the stack but instead to the size of a String.  This isn't always appropriate in all situations, you need to be sure you are not preserving information from one recursive call to the next.

The thing about trampolines is that trying to chain-jump onto the roof is how bones tend to get broken.  Which is why we don't have a trampoline, even though all of my children's friends do.

[code samples edited for line width]