Recursive Python Question - Where is n being updated?

Question

In this very classic recursive example, where is the variable n being updated?

Would you not have to

def factorial(n):
    if n <= 1: # BASE CASE
        return 1
    return n * factorial(n - 1) # RECURSIVE CALL

Why would you not have to have

def factorial(n):
        if n <= 1: # BASE CASE
            return 1
        return n * factorial(n - 1) # RECURSIVE CALL
        n = n - 1 ## why is something like this not needed?

*why is something like this not needed?* Why would it be needed? You aren't going to use `n` again, are you? — TheTridentGuy supports Ukraine, Jul 23 '23 at 18:48
you need to assign n to something like val ie val = n and n=n-1 and then to use recursion using `return val * factorial(n)` need to do in order to avoid all this unnecessary code, just use `return n * factorial(n-1)` — sahasrara62, Jul 23 '23 at 18:48
Imagine if, instead of making a recursive call, this code used the standard library `math.factorial` to compute the sub-result. Would you have the same question? Why not? **Why do you expect that this situation is different**? Calling the function recursively is just like calling any other function. It's just... calling a function. Aside from that: how are you expecting that it would ever have an effect to put code *after an unconditional `return`*? — Karl Knechtel, Jul 23 '23 at 19:48

score 0 · Accepted Answer · answered Jul 23 '23 at 18:48

The variable n does not have to be updated. We're making a new call to factorial with a reduced value of n. Each call to factorial only works with one n value. Consider how this works.

Say we call factorial(3), so n is 3. 3 is clearly not less than or equal to 1, so we get down to the return statement. We're going to multiply something by 3, but we don't know what yet. We then call factorial(2).

That starts a NEW call to factorial, unrelated to the original. In this call, n is still greater than 1, so we get to the return statement, and we start multiplying 2 by something. That something calls factorial(1).

In THIS call to factorial, n is less than or equal to 1, so we return 1.

Now we go back out to the second call, where we were in the middle of a multiplication. That line was basically:

    return 2 * factorial(1)

which we now know is

    return 2 * 1

so the second invocation returns 2. We now back out to the original invocation, where we had

    return 3 * factorial(2)

factorial(2) returned 2, so this becomes

    return 3 * 2

which returns 6 to the original caller.

n never gets updated. It's just that each new call to the function gets a reduced value.

Recursive Python Question - Where is n being updated?

1 Answers1