Do different types of recursion have different memory complexities?

Viewed 24

I was wondering if the 2 recursive functions below have different memory complexities:

1

def f(x):
    if x == 100:
        return 1
    return 1 + f(x + 1)
res = f(1) 
res # evaluates to 100

2

res = 1
def g(x):
    global res
    if x == 100:
        return
    res += 1
    g(x + 1)
g(1)
res # also evaluates to 100

From my understanding, it appears that since f's recursive calls are being returned, Python must keep all 100 function calls in the stack frame until x reaches 100. On the other hand, g's recursive calls are not returned, which means that the stack frame only needs to keep 1 function call at any given time. Therefore, f has linear memory complexity while g has constant. Is my understanding correct? Thanks!

0 Answers
Related