Week 5

What would recursion look like the wrong way round?

A few nights ago I had a dream. I was on an airplane. I don’t remember the details all that well, but I do have a few visual images of it. Then, at one point, I realized it was a dream, and I woke up. I went about my life for a while, lived various episodes. I was slightly puzzled about having realized that my dream was a dream—I’m not the kind of person who becomes aware of that fact while still dreaming. Then… I woke up again. I realized that I had actually still been having a dream that first time that I woke up and realized I had been dreaming. It was so Inceptiony. It was practically Inception 2.

Anyway, so this obviously has a parallel with recursion in that you go deeper and deeper into the same function. The problem is that the base case here feels like it should be waking life, not any of the dreams. That is to say, unlike in proper recursion, where you go deeper and deeper until you hit a solvable case, in the case of my dreams, the deeper you go into instances of the same function, you further you get from resolving it… so you will go infinitely deep.

I don’t know, I guess we could represent it in Python like this:

def recursive_dream(x):
    if x == 0:
        return x
    larger = recursive_dream(x + 1)
    smaller = larger - 1
    return smaller

Here we’re trying desperately to exit the dream by backing out to our base case of 0, but unfortunately our one operation on x is to make it larger. (The analogy might not be perfect.) You might feel like this will run the function x times. In fact it will go infinitely. Actually, you can’t really enter an infinite loop with recursion in Python, because it has a maximum recursion depth of 987, so you’ll get a RuntimeError.

How do we prove that this is infinite? Well, let’s trace it. What happens if we plug in 1 for x? Well, it’s not our base case of 0, so it calls the function with x + 1, i.e. 2. That calls it with 3… which calls it with 4… etc. So the function never gets to set the value of larger at any depth, nor subtract 1 from it to get smaller, nor return smaller.

So now let’s modify our code a little bit and add an upper limit, our own “maximum dream depth”. Think about it: what will the following code do?

def recursive_dream(x):
    if x == 0:
        return x
    if x == 50:
        return x
    larger = recursive_dream(x + 1)
    smaller = larger - 1
    return smaller

Okay, so now x will presumably == 50 at some point and we’ll hit our upper limit. So try to reason this out: what will recursive_dream(20) return? Trace it if you have to.

If you guessed an infinite loop, good thought but wrong. If you guessed 50, good thought but also wrong. It’ll return 20.

Tracing it again (by the “computer method”), if we pass 20 to our function, it’ll call itself with x + 1, i.e. 21. It’ll keep doing that until it calls itself with x = 50, which will trigger our upper limit case. That case returns x itself. Which means we now have a value for larger, i.e. 50. Next we subtract 1 from that to get smaller, i.e. 49, and we return that. Now, remember that this call is itself what’s setting larger for the next call in the stack, i.e. the next less deep call. Said less deep call will then subtract 1 from that to get its value for smaller, and return that… etc. Until the original call we made, with 20, receives the value 21 for larger, subtracts 1 to get its smaller value, and returns 20.

If it helps, remember that we can also trace this by the method zingarod calls the “human method” (in my opinion not necessarily more human, just the opposite direction). Don’t forget that we’re still working with a perversely inversed recursive function here, so our simpler case is nearer to the upper limit, not to the base case. So we should first ask ourselves, what does recursive_dream(50) return? Clearly 50 itself. So what does recursive_dream(49) return? Well, it calls recursive_dream(50). We know that that returns 50. Which our original call stores as larger, then subtracts 1 from to get 49, which it returns. Then you work out recursive_dream(48), plugging in recursive_dream(49) when it’s time to make that call, and pretty soon you realize that your tracing job is done.

Okay, we get that. Before we finish, let’s do one more odd thing for the sake of fun with our awful recursion. So, making our thoughts more convoluted, what will happen if we do… this?

def recursive_dream(x):
    if x == 0:
        return x
    if x == 50:
        return x + 1
    larger = recursive_dream(x + 1)
    smaller = larger - 1
    return smaller

What will recursive_dream(20) return? Again, try to trace it before you read the next sentence.

The answer, you’ll think, is that surely here it’ll be infinite. Surely! After all, we’ll never get a value for larger that allows us to exit the depth at the upper limit call and start working our way down the stack. That’s totes my own conclusion. Right?

Wrong. It returns 21.

If you’re frustrated, trace it again using the “human method”. So we try recursive_dream (50). Clearly this returns 51. Next, we work out recursive_dream(49). That will bypass our base and upper limit conditions and call itself with x + 1, i.e. recursive_dream(50). We know it returns 51, so 51 is the value for larger back at the recursive_dream(49) call. So the value for smaller is 50, and is returned. Now, again with recursive_dream(48). This calls recursive_dream(49), which we know returns 50. So 50 is the value for larger at the level of recursive_dream(48), and thus smaller is 49, which is what’s returned. It’ easy to extrapolate why recursive_dream(20) returns 21.

Okay, one last one. But I’ll leave you with this one, because it should be cake by now. So far we’ve had the +1 and -1 operations be exactly even. What happens if we unbalance them? That is to say, what does recursive_dream(20) do if we use the following version?

def recursive_dream(x):
    if x == 0:
        return x
    if x == 50:
        return x + 10
    larger = recursive_dream(x + 1)
    smaller = larger - 1
    return smaller

Enjoy! Don’t forget to trace! 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s