Блог

Главная - Вопросы по программированию - Голова Питона против Хвостовая рекурсия — Нет ошибки стекового потока для головы и, кажется, работает лучше?

Голова Питона против Хвостовая рекурсия — Нет ошибки стекового потока для головы и, кажется, работает лучше?

#python #recursion

Вопрос:

 import sys
sys.setrecursionlimit(15000)

import time

def factorialHead(n):
    if n <= 1: 
        return 1
    else: 
        return n * factorialHead(n - 1)

print("Head Recursion:")
now = time.time()
factorialHead(10000) # this should break as I understand - stackoverflow (seems to work fine??)
print(time.time() - now)

def factorialTail(n, currentValue = 1):
    if n <= 1: 
        return currentValue
    else:
        return factorialTail(n-1, n*currentValue)

print("Tail Recursion:")
now = time.time()
factorialTail(10000)
print(time.time() - now)

# Output:
# Head Recursion:
# 0.02311873435974121
# Tail Recursion:
# 0.05035591125488281

#Switched Order
# Tail Recursion:
# 0.05422401428222656
# Head Recursion:
# 0.017311573028564453

Несколько новичок в python и кодировании в целом. Играл с некоторыми рекурсивными функциями головы и хвоста и заметил некоторое странное поведение в рекурсивной функции головы. Это своего рода «воссоздание» того, с чем я столкнулся. Насколько я понимаю стек, приведенная выше рекурсия head должна выдавать ошибку stackoverflow. Он не только не делает этого, но, похоже, работает лучше, чем хвостовой рекурсивный эквивалент.
Может кто-нибудь, пожалуйста, объяснить, что здесь происходит, что я упускаю?

Python=3.8.10 (только для справки)

Комментарии:

1. ну, для начала, вы должны знать, что в Python нет оптимизации хвостовых вызовов, поэтому и то, и другое должно вызывать ошибку рекурсии на одинаковой глубине.

2. В любом случае, вы установили максимальный предел рекурсии 15000 , почему вы ожидаете , что он нарушится 10000 ??? Обратите внимание, что и то, и другое ломается, если вы используете headRec(15000) и tailRec(15000) вызываете ожидаемую ошибку

3. Прежде всего, одного эксперимента недостаточно. Во-вторых, вы должны использовать timeit , а не одноразовую time.time ссылку, чтобы уменьшить шум в ваших наблюдениях. В-третьих, поскольку Python обычно не оптимизирует хвостовые вызовы, вы пытаетесь измерить то, чего нет в вашей системе времени выполнения. Далее, как сказал Хуан, сначала вы не достигли указанного вами предела стека, поэтому совсем не ясно, почему вы ожидаете, что ваша программа будет выдавать и исключать.

4. Для иллюстрации того, как реализовать правильную хвостовую рекурсию в Python, см. Этот блог .

5. Наконец, поскольку обе функции повторяются на одной и той же глубине, почему вы думаете, что именно одна из них должна ошибаться? Вы хотите, чтобы рекурсия была сведена к циклу?

Метки: , ,