I kept at writing a sleepy-bear program, and I feel a little better now. Here’s what I learned. VBA can only recurse to a maximum depth of about 6,000 or 7,000 calls. Tail recursion and head recursion both max out at the same depth. No optimization for tail recursion takes place.
Furthermore, I learned that the sleepy-bear program is a great example of head recursion COMBINED WITH tail recursion. Three phases of recursion take place: first, you deepen the story; second, you report the bottom-level of the story, third you wrap up each previous level of the story. Phase One performs head recursion to push each insomniac animal onto the stack. Phase Two occurs when the stack hits bottom—recursion reaches its pre-determined maximum depth and reports a sleepy animal who buys the story. Phase Three performs tail recursion to unwind the stack; each insomniac sub-story gets a happy ending all the way back up the stack—until the original baby bear finally falls asleep.
I built and tested the sleepy-bear idea in stages. First, I made a NON-recursive program consisting of 2 separate, consecutive FOR-NEXT loops that performed the string-handling. My first loop introduced insomniac animals 1 through 4; then I put a 5th animal to sleep between the two loops; then I looped out, putting animals 4 through 1 to sleep. In the second stage, I wrote a heads-and-tails numeric recursion framework that merely counted from 1 to 20 going in and counted back from 20 to 1 coming out:
Third, I fleshed out this numeric recursion framework to concatenate boiler-plate narrative text using reasonably cool animal names taken from a hard-coded string array:
String concatenation looks naturally stinky, so I recommend reading the simpler numeric recursion subroutine first, to visualize what heads-and-tails recursion actually does. Note that my simple numeric recursive subroutine outputs the final stack value, 20, twice—which does not serve the animal narrative correctly. It’s a worthwhile exercise to fix this numeric recursion framework so that it puts the number 20 to sleep only once!
Next consider my claim that VBA recursion maxes out with a stack-overflow error after 6,000 or 7,000 calls. I verified this claim by stress-testing my numeric framework subroutine whilst pushing single integers onto the stack during each recursion. What if I had decided to push the entire “story-so-far” onto the sleepy animal stack? (In reality, I choose to make my text-narrative recursion perform its cumulative work upon a general declaration variable, BedtimeStory, outside the recursion stack.) For sure, a fat string stack would never make it to 6,000 calls! On the other hand, the fat stack would provide its own opportunity to observe and experiment with how much raw stack space VBA is actually willing to allocate. (C# has its own allocation attitudes, but I digress. Don’t even get me started on the charms of the .NET StringBuilder object)
In summary, I think creating a deliberately string-clogged VBA stack is a worthwhile exercise—up to a point. Deliberate stack-clogging is a way to make recursion feel physical, not just logical.
After all this, do I like recursion better now than I used to? Well yes, but only a little.