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

推荐订阅源

Jina AI
Jina AI
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
有赞技术团队
有赞技术团队
罗磊的独立博客
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
U
Unit 42
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
Recent Announcements
Recent Announcements
Y
Y Combinator Blog
Vercel News
Vercel News
Martin Fowler
Martin Fowler
V
V2EX
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
L
LangChain Blog
云风的 BLOG
云风的 BLOG
H
Hackread – Cybersecurity News, Data Breaches, AI and More
aimingoo的专栏
aimingoo的专栏
G
Google Developers Blog
The GitHub Blog
The GitHub Blog
N
Netflix TechBlog - Medium
Google DeepMind News
Google DeepMind News
雷峰网
雷峰网
阮一峰的网络日志
阮一峰的网络日志
F
Fortinet All Blogs

博客园 - 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只对自递归起作用,还不能用于互递归。