Как я могу сосчитать рекурсивные вызовы функции в Python?

Question

Я играл с рекурсивной функцией Аккерманна. Для определенных значений моя подсказка не будет отображать все вычисленные выходные данные, потому что Python настолько быстро превысит свой рекурсивный предел, что заморозит подсказку до того, как "легкие" части ее догонят.

Поэтому я подумал, что смогу добавить рекурсивный счетчик и быструю паузу после полного выполнения функции. Я получал ожидаемые результаты, пока он не достиг значений (1,0). После этого я получил TypeError: can only concatenate tuple (not "int") to tuple,

Мой код выглядит следующим образом:

import time
import sys
sys.setrecursionlimit(3000)

def ackermann(i,j,rec):
    output = None
    if i==0:
        output = j+1
    elif j==0:
        output = ackermann(i-1,1,rec)
        rec=rec+1
    else:
        output = ackermann(i-1,ackermann(i,j-1,rec),rec)
        rec=rec+1
    return output,rec

rec=0
for i in range(5):
    for j in range(5):
        print("(",i,",",j,")= ",ackermann(i,j,rec))
        time.sleep(2)

Обратите внимание, что удаление всех экземпляров rec (мой счетчик повторений), программа работает нормально. (Вы можете увидеть все выходы для значений i,j = 3)

Может кто-нибудь указать, как исправить мой код, или предложить другой метод определения того, сколько раз функция Аккерманна вызывает себя?

Кроме того, я заметил, что ограничение в 5000 может привести к быстрому падению моего ядра Python. Есть ли верхний предел?

Я использую последнюю Анаконду.

РЕДАКТИРОВАТЬ

Я попытался реализовать ту же функцию, используя список в качестве параметра со следующими данными [i,j,output,#recursion]

import time
import sys
sys.setrecursionlimit(3000)

def ackermann(*rec):
    rec=list(rec)
    print(rec) # see the data as they initialize the function
    if rec[0][0]==0:
        rec[0][1]=rec[0][1]+1
        rec[0][2] = rec[0][1]+1
    elif rec[0][1]==0:
        rec[0][0]=rec[0][0]-1
        rec[0][1]=1
        rec = ackermann()
        rec[0][3]=rec[0][3]+1
    else:
        rec[0][0]=rec[0][0]-1
        rec[0][1] = ackermann()
        rec = ackermann()
        rec[0][3]=rec[0][3]+1
    return rec

for i in range(5):
    for j in range(5):
        rec=[i,j,0,0]
        print(ackermann(rec))
        time.sleep(1)

Но на этот раз я получаю IndexError: list index out of rangeпотому что по неизвестной причине мой список опустошается

ВЫХОД:

[[0, 0, 0, 0]]
[[0, 1, 2, 0]]
[[0, 1, 0, 0]]
[[0, 2, 3, 0]]
[[0, 2, 0, 0]]
[[0, 3, 4, 0]]
[[0, 3, 0, 0]]
[[0, 4, 5, 0]]
[[0, 4, 0, 0]]
[[0, 5, 6, 0]]
[[1, 0, 0, 0]]
[]

Answer 1

Проблема с оригинальной реализацией состоит в том, чтоreturn output, rec с радостью создаст кортеж, когда output и rec оба являются числами, что верно, когда i=0. Но как только вы доберетесь до i=1, j=0, функция вызывает Ackerman для (0,1,rec), которая возвращает кортеж, к которому она затем не может добавить целое число rec, отсюда и сообщение об ошибке. Я полагаю, что работал с этой идеей, хотя, почти без изменений, за исключением того, что вместо того, чтобы пытаться передать и вернуть rec, я сделал ее глобальной (безобразно, я знаю). Я также переформатировал вывод, чтобы лучше прочитать. Таким образом:

import time
import sys
sys.setrecursionlimit(3000)
def ackermann(i,j):
    global rec
    output = None
    if i==0:
        output = j+1
    elif j==0:
        output = ackermann(i-1,1)
        rec=rec+1
    else:
        output = ackermann(i-1,ackermann(i,j-1))
        rec=rec+1
    return output


for i in range(5):
    for j in range(5):
        rec = 0
        print
        print("ack("+str(i)+","+str(j)+") = "+str(ackermann(i,j)))
        print("rec = "+str(rec))
        print
        time.sleep(1)

и вывод, перед ошибкой, является,

ack(0,0) = 1
rec = 0


ack(0,1) = 2
rec = 0


ack(0,2) = 3
rec = 0


ack(0,3) = 4
rec = 0


ack(0,4) = 5
rec = 0


ack(1,0) = 2
rec = 1


ack(1,1) = 3
rec = 2


ack(1,2) = 4
rec = 3


ack(1,3) = 5
rec = 4


ack(1,4) = 6
rec = 5


ack(2,0) = 3
rec = 3


ack(2,1) = 5
rec = 8


ack(2,2) = 7
rec = 15


ack(2,3) = 9
rec = 24


ack(2,4) = 11
rec = 35


ack(3,0) = 5
rec = 9


ack(3,1) = 13
rec = 58


ack(3,2) = 29
rec = 283


ack(3,3) = 61
rec = 1244


ack(3,4) = 125
rec = 5213


ack(4,0) = 13
rec = 59

Мне кажется, что есть только одно или два других значения (4, 4, я думаю, что оно захлебнется, несмотря ни на что, поэтому сначала нужно получить 5, 0), вы можете надеяться выбраться таким образом, независимо от того, как много ты возиться.

Я немного обеспокоен тем, что rec превышает предельное значение рекурсии, но я думаю, что Python должен каким-то образом интерпретировать его, чтобы он стал глубже, чем можно было подумать, или я не до конца понимаю sys.recursionlimit (я посмотрел в rec несколько раз, и, по крайней мере, я последовал вашему примеру по его вычислению, а также, в качестве проверки работоспособности, я изменил порядок увеличения и вызова функции и получил те же результаты).

РЕДАКТИРОВАТЬ: я добавил еще один параметр, чтобы отслеживать, насколько глубоко любой конкретный вызов когда-либо повторяется. Это, как правило, меньше, чем (и самое большее на один) "rec". rec представляет (фактически на 1 меньше), сколько раз вызывается функция для выполнения конкретного вычисления, но не все из них должны быть одновременно в стеке интерпретатора Python.

Пересмотренный код:

import time
import sys
sys.setrecursionlimit(3000)
def ackermann(i,j,d):
    global rec
    global maxDepth
    if ( d  > maxDepth ) : maxDepth = d
    output = None
    if i==0:
        output = j+1
    elif j==0:
        rec=rec+1
        output = ackermann(i-1,1, d+1)
    else:
        rec=rec+1
        output = ackermann(i-1,ackermann(i,j-1, d+1),d+1)
    return output


for i in range(5):
    for j in range(5):
        rec = 0
        maxDepth=0
        print
        print("ack("+str(i)+","+str(j)+") = "+str(ackermann(i,j,1)))
        print("rec = "+str(rec))
        print("maxDepth = "+str(maxDepth))
        print
        time.sleep(1)

пересмотренный вывод (прежде чем он сдастся)

ack(0,0) = 1
rec = 0
maxDepth = 1


ack(0,1) = 2
rec = 0
maxDepth = 1


ack(0,2) = 3
rec = 0
maxDepth = 1


ack(0,3) = 4
rec = 0
maxDepth = 1


ack(0,4) = 5
rec = 0
maxDepth = 1


ack(1,0) = 2
rec = 1
maxDepth = 2


ack(1,1) = 3
rec = 2
maxDepth = 3


ack(1,2) = 4
rec = 3
maxDepth = 4


ack(1,3) = 5
rec = 4
maxDepth = 5


ack(1,4) = 6
rec = 5
maxDepth = 6


ack(2,0) = 3
rec = 3
maxDepth = 4


ack(2,1) = 5
rec = 8
maxDepth = 6


ack(2,2) = 7
rec = 15
maxDepth = 8


ack(2,3) = 9
rec = 24
maxDepth = 10


ack(2,4) = 11
rec = 35
maxDepth = 12


ack(3,0) = 5
rec = 9
maxDepth = 7


ack(3,1) = 13
rec = 58
maxDepth = 15


ack(3,2) = 29
rec = 283
maxDepth = 31


ack(3,3) = 61
rec = 1244
maxDepth = 63


ack(3,4) = 125
rec = 5213
maxDepth = 127


ack(4,0) = 13
rec = 59
maxDepth = 16

Answer 2

В вашей отредактированной версии кода вы использовали *arg в своем определении для ackerman и явно сделали его списком, и вы получите одиннадцать выходных списков, содержащих список по четыре элемента в каждом, пока в двенадцатой рекурсии вы не получите пустой список. Итак, были ли первые одиннадцать списков ожидаемыми элементами в соответствии с ограничениями Аккермана? Кроме того, в двенадцатой рекурсии вы говорите, что список "опустошен". Интересно, для аналитических целей имеет ли смысл говорить, что он не был заполнен в первую очередь. То есть не то, что что-то опустошило, а то, что что-то не заполнило, как ожидалось, в двенадцатый раз.