Python recursive optimization

2019-08-2020:43:28 Comment
Excerpt

the beautiful style python recursive code, avoids depth exceeded.

the beautiful style python recursive code, avoids depth exceeded.

First, Let's execute the common python recursive code. We'll find maximum 996 depth exceeded.

def fib(count, cur=0, next_=1):
    if count <= 1:
        return cur
    else:
        # Notice that this is the tail-recursive version
        # of fib.
        return fib(count-1, next_, cur + next_)

print fib(996)
RuntimeError: maximum recursion depth exceeded
>>>

Let's execute the other version code.

def fib(count, cur=0, next_=1):
    if count <= 1:
        yield cur
    else:
        # Notice that this is the tail-recursive version
        # of fib.
        yield fib(count-1, next_, cur + next_)
print fib(996)
<generator object fib at 0x02B00D00>

This shows we can use yield statement replace return statement, change it to generator. It does not execute immediately, and avoids depth exceeded.
Let study the good code.

import types

def tramp(gen, *args, **kwargs):
    g = gen(*args, **kwargs)
    while isinstance(g, types.GeneratorType):
        g=g.next()
    return g
print tramp(fib, 996)
#result
3919377061614427623668052985592742430389065042819420493170692719480242247392252775480208752179017313071371501566248877239254299341332131655760767122899079117071192049598939666199865808814650408864891823186505

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: