Understanding recursion in Python with if case

Question

In solving this codewars challenge I came across a recursion example I don't understand.

The challenge is to give the next nth numbers, given an initial 3 number seed sequence, where the nth numbers are determined by adding the last three numbers of the sequence.

So for the seed sequence list of [1,2,3] and given n=5, you'd return the following:

1 + 2 + 3 = 6
2 + 3 + 6 = 11

Answer:
[1, 2, 3, 6, 11]

I solved the problem with the following:

def tribonacci(sequence,n):
if n <=3:
    return sequence[:n]
else:
    for i in range(n-3):
        sequence.append(sum(signature[-3:]))        
    return sequence

In reviewing the other solutions, I came across this very elegant solution that uses recursion:

def tribonacci(sequence,n):
    return sequence[:n] if n<=len(sequence) else tribonacci(sequence + [sum(sequence[-3:])],n)

My question is: why doesn't this just run infinitely? I'm having trouble understanding why this terminates with the nth iteration. It doesn't seem like the function of 'n' is stipulated anywhere, except in the if case.

As an experiment, I modified the code to ignore the less-than-or-equal-to-length-of-sequence case, like so:

def tribonacci(sequence,n):
    return tribonacci(sequence + [sum(sequence[-3:])],n)

And this does run infinitely and errors out with a runtime error of max recursion depth.

So obviously the case option is what seems to control the termination, but I can't see why. I've used recursion myself in solves (for instance in creating a factoring function), but in that example you subtract n-1 as you iterate so there's a terminating process. I don't see that happening here.

I guess I don't completely understand how the return function works. I was reading it as:

return n-item list if n is less/equal to sequence length

else

rerun the function

Perhaps I should actually be reading it as:

return n-item list if n is less/equal to sequence length

else

return n-item list after iterating through the function enough times to fill a n-item list

Answer 1

At each level of recursion, the sequence becomes longer because of concatenation (+). Eventually it will become long enough for n to become less than length.

Answer 2

You can rewrite this:

a = b if p else c

as this:

if p:
    a = b
else:
    a = c

Knowing that, you can see that this:

def tribonacci(sequence,n):
    return sequence[:n] if n<=len(sequence) else tribonacci(sequence + [sum(sequence[-3:])],n)

is the same as:

def tribonacci(sequence,n):
    if n <= len(sequence):
        return sequence[:n]
    else:
        return tribonacci(sequence + [sum(sequence[-3:])],n)

Now you should be able to see that there's a condition controlling that the recursion doesn't go on for ever.