summa_n.py

import traceback

n = 6

# Рекурсия.
def summa_n1(x):
    global n_calls
    global max_stack
    n_calls += 1
    l = len(traceback.extract_stack())
    max_stack = max(l, max_stack)
    print(f"{l:2} ({n_calls:2}): {l * '*' + ': ' + str(x)}")

    if x == 0:
        return 0
    else:
        return x + summa_n1(x - 1)

n_calls = 0
max_stack = 0
print(summa_n1(n), max_stack)

# Хвостовая рекурсия (никакой разницы, тк в питоне нету tail call
# optimisation). Различия см.
# https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-11.html#%_sec_1.2.1 .
def summa_n2(x, s):
    global n_calls
    global max_stack
    n_calls += 1
    l = len(traceback.extract_stack())
    max_stack = max(l, max_stack)
    print(f"{l:2} ({n_calls:2}): {l * '*' + ': ' + str(x)}")

    if x == 0:
        return s
    else:
        return summa_n2(x - 1, x + s)

n_calls = 0
max_stack = 0
print(summa_n2(n, 0), max_stack)

# CPS (continuation passing style).
def id(x):
    return x

def summa_n3(x, k):
    global n_calls
    global max_stack
    n_calls += 1
    l = len(traceback.extract_stack())
    max_stack = max(l, max_stack)
    print(f"{l:2} ({n_calls:2}): {l * '*' + ': ' + str(x)}")

    if x == 0:
        return k(0)
    else:
        return summa_n3(x - 1, lambda y: k(x + y))

n_calls = 0
max_stack = 0
print(summa_n3(n, id), max_stack)

# CPS with shift/reset. По сути просто остановка после каждой итерации.
# См. https://okmij.org/ftp/continuations/#tutorial .
def summa_n4(x, k):
    global n_calls
    global max_stack
    n_calls += 1
    l = len(traceback.extract_stack())
    max_stack = max(l, max_stack)
    print(f"{l:2} ({n_calls:2}): {l * '*' + ': ' + str(x)}")

    if x == 0:
        return lambda: k(0)
    else:
        return lambda: summa_n4(x - 1, lambda y: k(x + y))

n_calls = 0
max_stack = 0
f = summa_n4(n, id)
while callable(f):
    f = f()
print(f, max_stack)