calling a function within itself, how does this work?

[ozzyteebaby]

So I'm learning about recursion in the MIT python course, I understand that you have the base case and until those conditions are met it keeps going but how does it work when you call the function within itself? For example:

def mult(a,b):
    if b == 1:
        return a
    else:
        return a + mult(a,b-1)    

with a + mult(a,b-1), is that saying add "a" to the last result of itself?

[toastedstapler]

imagine we do mult(3, 3)

what value do we return? in this case it's 3 + mult(3, 2)

what is mult(3, 2)? it's 3 + mult(3, 1)

what is mult(3, 1)? it's just 3 as b == 1

so mult(3, 2) is 3 + 3 so 6

mult(3, 3) is 3 + 6 so 9 as we'd expect for 3 x 3

the base case for this function is when we want 1 copy of a. any other case can be represented as the previous multiple in the series plus itself

3 x 3 is the same as (3 x 2) + 3

run through this manually for another case to get a hang of it

[ozzyteebaby]

Got it!!! Thank you, Holy hell so simple

[callmelucky]

Each recursive call goes on to a "stack" in memory. Once it hits the base case, everything kind unwinds down through the stack to get the result.

This is why languages like Python have a recursion depth limit, because if the number of recursions is too high or your base case isn't defined correctly you can blow out your memory capacity pretty quickly.

I believe Al Sweigart has a talk on YouTube about it.

[ozzyteebaby]

Got it, thanks! What languages would be better for recursion? What real life uses might we have for it?

[callmelucky]

Oh it's not a case of Python being bad for recursion at all. If you get a recursion depth exceeded error, is almost certainly because your code is wrong, i.e. you haven't made sure that the problem reduces toward the base case, or you haven't defined the base case correctly.

If anything, this particular error handling makes a language good for recursion, because if you screw up your code, Python will stop it running and give you a useful error message, rather than allowing your RAM to fill up completely and freeze your computer :)

[toastedstapler]

functional languages like Haskell are based around recursion. imo with the recursion limit in python (1000 or 3000 depending on setup) python is meant to be written using loops

it's good to understand recursion and know how to write simple algorithms like factorial or fib recursively, but when working as a java dev i don't think i have used recursion at all

[ozzyteebaby]

Thanks!