[pypy-issue] [issue1342] Recursion question

Senyai tracker at bugs.pypy.org
Tue Nov 27 21:02:28 CET 2012


New submission from Senyai <senyai at gmail.com>:

Hello.

I wonder why recursion is so fast compared to linear approach.

----------
files: recursion_question.py
messages: 5046
nosy: pypy-issue, senyai
priority: wish
status: unread
title: Recursion question

________________________________________
PyPy bug tracker <tracker at bugs.pypy.org>
<https://bugs.pypy.org/issue1342>
________________________________________
-------------- next part --------------
import timeit

val = 9450847
_base = 62

def rec(n, ret):
    a, b = divmod(n, _base)
    ret.append(b)
    if a:
        return rec(a, ret)
    ret.reverse()
    return ret

def lin(n):
    ret = []
    while n:
        n, b = divmod(n, _base)
        ret.append(b)
    ret.reverse()
    return ret

for i in xrange(3):
    print "l", timeit.Timer('lin(val)', 'from __main__ import lin, val').timeit(number=1000000)
    print "r", timeit.Timer('rec(val, [])', 'from __main__ import rec, val').timeit(number=1000000)


More information about the pypy-issue mailing list