Don't forget to also checkout my second blog containing articles to all other related ICT topics!!

Sunday, May 6, 2012

Python does not support 'Tail recursion'

Some programming languages support tail recursion for optimizing away tail calls, but Python definitely isn't one of them. Scala on the other hand does.
def fact_using_tailracursion(i):
    def f(n, accumulator): 
        if (n == 0):
            return accumulator
        else:
            return f(n - 1, n * accumulator)
    return f(i,1)

def fact(i):
    if (i <= 0):
        return 1
    else:
        return i * fact(i - 1) 

import cProfile
cProfile.run('fact_using_tailracursion(400)')
cProfile.run('fact(400)')

         404 function calls (4 primitive calls) in 0.236 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.236    0.236 :1()
        1    0.000    0.000    0.236    0.236 t.py:1(fact_using_tailracursion)
    401/1    0.236    0.001    0.236    0.236 t.py:2(f)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


         403 function calls (3 primitive calls) in 0.230 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.229    0.229 :1()
    401/1    0.229    0.001    0.229    0.229 t.py:9(fact)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

No comments:

Post a Comment