Я пытаюсь сравнить время выполнения факториальных функций разных реализаций. Тем не менее, я обнаружил, что хвостовая рекурсивная версия факториальной функции намного медленнее, чем итеративная и не хвостовая рекурсивная версия, и я не могу найти объяснения этому. Вот моя реализация кода. Я использую Python 3.7.4 для проверки кода.
import sys
from line_profiler import LineProfiler
sys.setrecursionlimit(20000)
def fact_iter(n):
"""Return the factorial of n, using iteration"""
product = 1
for i in range(2, n + 1):
product *= i
return product
def fact_non_tail_recur(n):
"""Return the factorial of n, using non-tail recursion"""
if n == 1:
return 1
product = n * fact_non_tail_recur(n - 1)
return product
def fact_tail_recur(n, product=1):
"""Return the factorial of n, using tail recursion"""
if n == 1:
return product
product *= n
return fact_tail_recur(n - 1, product)
def fact_tail_recur_2(n, i=1, product=1):
if i == n:
return product * i
product *= i
return fact_tail_recur_2(n, i+1, product)
def profile(f):
lp = LineProfiler()
lp_wrapper = lp(f)
lp_wrapper(10000)
lp.print_stats()
if __name__ == '__main__':
profile(fact_iter)
profile(fact_non_tail_recur)
profile(fact_tail_recur)
profile(fact_tail_recur_2)
А вот профиль времени выполнения функций.
Timer unit: 1e-06 s
Total time: 0.040521 s
File: fact.py
Function: fact_iter at line 6
Line # Hits Time Per Hit % Time Line Contents
==============================================================
6 def fact_iter(n):
7 """Return the factorial of n, using iteration"""
8 1 2.0 2.0 0.0 product = 1
9 10000 13513.0 1.4 33.3 for i in range(2, n + 1):
10 9999 27005.0 2.7 66.6 product *= i
11 1 1.0 1.0 0.0 return product
Timer unit: 1e-06 s
Total time: 0.042846 s
File: fact.py
Function: fact_non_tail_recur at line 14
Line # Hits Time Per Hit % Time Line Contents
==============================================================
14 def fact_non_tail_recur(n):
15 """Return the factorial of n, using non-tail recursion"""
16 10000 13389.0 1.3 31.2 if n == 1:
17 1 2.0 2.0 0.0 return 1
18 9999 16481.0 1.6 38.5 product = n * fact_non_tail_recur(n - 1)
19 9999 12974.0 1.3 30.3 return product
Timer unit: 1e-06 s
Total time: 0.085538 s
File: fact.py
Function: fact_tail_recur at line 22
Line # Hits Time Per Hit % Time Line Contents
==============================================================
22 def fact_tail_recur(n, product=1):
23 """Return the factorial of n, using tail recursion"""
24 10000 13812.0 1.4 16.1 if n == 1:
25 1 2.0 2.0 0.0 return product
26 9999 55390.0 5.5 64.8 product *= n
27 9999 16334.0 1.6 19.1 return fact_tail_recur(n - 1, product)
Timer unit: 1e-06 s
Total time: 0.07916 s
File: fact.py
Function: fact_tail_recur_2 at line 30
Line # Hits Time Per Hit % Time Line Contents
==============================================================
30 def fact_tail_recur_2(n, i=1, product=1):
31 10000 13521.0 1.4 17.1 if i == n:
32 1 12.0 12.0 0.0 return product * i
33 9999 49390.0 4.9 62.4 product *= i
34 9999 16237.0 1.6 20.5 return fact_tail_recur_2(n, i+1, product)
График времени работы, измеренный как timeit
