⛽Recursive Leap of Faith

Jump Jump Jump!

Let's consider our factorial problem again:

def factorial(n):
    '''
    Accepts a non-negative number n and returns the factorial of that number.
    '''
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

Consider calculating factorial(150). Imagine writing the tree out for this the way we did for factorial(4) in the previous section. Go ahead and try it! You'll see that it gets absurdly big very fast.

Instead, we'll do something known as the recursive leap of faith. It goes like this: if we believe our base case is correct, that we'll reach our base case eventually, and that our recursive step is formatted properly, then we can assume that the recursive call will always return the correct value.

What this means is that, if our function works correctly, we can assume that the call factorial(149) returns to us the correct value. If it does so, we can multiply it with 150 to get factorial(150). This is the recursive leap of faith.

Taking the recursive leap of faith is one of the hardest things you'll have to do in this class. It requires you to believe that the code you wrote is correct... but you can often only write correct recursive code if you take the recursive leap of faith. A bit of a Catch-22. So, don't worry if you're not there yet! It takes time.

Over the next few sections, we'll go through recursive questions, see how they work behind the scenes, and in doing so, develop some faith in the recursive process.