惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

S
Secure Thoughts
罗磊的独立博客
T
The Blog of Author Tim Ferriss
人人都是产品经理
人人都是产品经理
博客园 - 叶小钗
Last Week in AI
Last Week in AI
美团技术团队
Google Online Security Blog
Google Online Security Blog
Application and Cybersecurity Blog
Application and Cybersecurity Blog
D
Docker
G
Google Developers Blog
大猫的无限游戏
大猫的无限游戏
酷 壳 – CoolShell
酷 壳 – CoolShell
小众软件
小众软件
月光博客
月光博客
L
LINUX DO - 最新话题
cs.AI updates on arXiv.org
cs.AI updates on arXiv.org
CTFtime.org: upcoming CTF events
CTFtime.org: upcoming CTF events
W
WeLiveSecurity
H
Heimdal Security Blog
Vercel News
Vercel News
SecWiki News
SecWiki News
Forbes - Security
Forbes - Security
Blog — PlanetScale
Blog — PlanetScale
Google DeepMind News
Google DeepMind News
Exploit-DB.com RSS Feed
Exploit-DB.com RSS Feed
www.infosecurity-magazine.com
www.infosecurity-magazine.com
TaoSecurity Blog
TaoSecurity Blog
T
Troy Hunt's Blog
A
About on SuperTechFans
C
Check Point Blog
S
Security Affairs
Hacker News - Newest:
Hacker News - Newest: "LLM"
AI
AI
WordPress大学
WordPress大学
K
KPMG report finds enterprise disconnect between AI and its ROI | CIO
Help Net Security
Help Net Security
博客园_首页
The Last Watchdog
The Last Watchdog
S
SegmentFault 最新的问题
Hugging Face - Blog
Hugging Face - Blog
Security Archives - TechRepublic
Security Archives - TechRepublic
Engineering at Meta
Engineering at Meta
cs.CV updates on arXiv.org
cs.CV updates on arXiv.org
I
Intezer
K
Kaspersky official blog
M
MIT News - Artificial intelligence
J
Java Code Geeks
G
GRAHAM CLULEY
P
Palo Alto Networks Blog

博客园 - yushih

初学Erlang,写两个程序玩玩 Django杂记: super与metaclass,locmem有害 一直没弄明白的事--为什么招聘要求会有“面向对象分析与设计”这一项 用Linux的iptables和Python模拟广域网 Python programming with goto 实用主义之过--Pragmatic Version Control using Subersion, 2nd Ed.的书评 Python把C语言打得满地找牙 STL的binary search算法正确性的初步说明 关于文档标准之争的一点旁注 有关Ruby eval的一点编程风格 Design pattern一来,动态语言就笑了 - yushih - 博客园 完全没有领会“电子商务”的真谛 超级奇怪的F#格式错误 JAOO的魅力所在 一个Ruby idiom F#的一点糖 C++ hack:将C++编译器的类型检查转化为SLR(1)解析器 Quotes The Ruby Programming Language第一版非官方修正
信春哥!Python递归原地满状态变显式堆栈!入教即送尾递归优化!
yushih · 2010-01-07 · via 博客园 - yushih
问题:

有Python函数一枚,用递归写成。运行时超出Python的递归深度,现欲将其由在堆栈中分配空间改为在堆中分配空间(即用malloc)。

解决方法:

首先,from heaprecursion import *。然后对目标函数进行改造,假设要改造的递归函数为def func(p1, p2):

1.把函数中的递归调用func(exp1,exp2)改成yield RECURSION(exp1,exp2),即把所有"func"替换成"yield RECURSION"。

2.把函数中所有的"return"替换成yield。如果是尾递归return func(exp1, exp2)则改成yield TAIL(exp1, exp2)。

最后这样调用改造好的函数:heaprun(f, exp1, exp2)

例子:

from heaprecursion import *def sumlist(l):
    
if len(l)==0: return 0
    x
=l.pop()
    y
=sumlist(l)
    
return x+y

改造成这样:    

def sumlist2(l):
    
if len(l)==0: yield 0
    x
=l.pop()
    y
=yield RECURSION (l)
    
yield x+y; 
调用:
heaprun(sumlist2, range(
10000))
    
def factorial(n, accu):
    
if n==0:
        
return 1
    
else:
        
return factorial(n-1, accu*n)
改造成这样:
def factorial2(n, accu):
    
if n==0:
        
yield accu
    
else:
        
yield TAIL(n-1, accu*n)
调用:
heaprun(factorial2, 
100001)

t

=(1,
   (
2,
    
4,
    (
5,
     
6,
     
7)),
   (
3,
    
8,
    
9))def inorder(t):
    
if type(t) is int:
        
print t
    
else:
        inorder(t[
1])
        
print t[0]
        inorder(t[
2])
改造成这样:
def inorder2(t):
    
if type(t) is int:
        
print t
    
else:
        
yield RECURSION(t[1])
        
print t[0]
        
yield TAIL(t[2])
调用:
heaprun(inorder2, t)

heaprecursion.py代码如下:

def forward(it, arg):
    
# move iterator 'it' by calling 'next'(when 'arg' is None) or 'send'
    # return what 'next' or 'send' returns, or None if 'it' is at its end
    try:
        
if arg==None:
            
return it.next()
        
else:
            
return it.send(arg)
    
except StopIteration: pass
    
return Noneclass RECURSION(object):
    
def __init__(self, *args):
        self.args
=args
    
class TAIL(RECURSION):
    
passdef heaprun(f, *args):
    stack
=[f(*args)]
    param
=None
    
while(1):
        v
=forward(stack[-1], param)
        
if isinstance(v, RECURSION):
            
if type(v)==TAIL:
                stack.pop()
            stack.append(f(
*(v.args)))
            param
=None
        
else:
            stack.pop()
            
if stack:
                param
=v
            
else:
                
return v

 限制:

目前heaprecursion.py只对自递归起作用,还不能用于互递归。