CWYAlpha

Just another WordPress.com site

Thought this was cool: 不定义函数实现递归(python)

leave a comment »


不定义函数?那么我们就无法重复利用自身的代码了吗?不,自动机理论中的递归原理的引理告诉我们,一个函数可以得到其自身(读取源文件这种方法无视之),只需要这么做:

A = r'''B = "A = r\'''" + A + "\'''\n" + A
print B'''
B = "A = r\'''" + A + "\'''\n" + A
print B

原理就是分两步,运行时先写下来接下来要做什么(A),然后接下来根据刚才写的就构造出前面和后来都要做些什么,既是整个源程序了。构造过程相反,因为接下来这个过程是确定的,所以先写出接下来,再反填回A。

wr 给的这个链接里的许多程序就是这个原理,虽然比我这个短,但是我这个的好处是接下来这个过程可以随便写,反填时还保持原格式,下面我们利用这个特点实现一个不定义函数的递归程序。

得到程序自身后,当然需要再次运行它,我们利用 exec 这个相当于通用图灵机的函数。因为 exec 默认使用和修改当前的全局和本地变量,所以我们给他加一个虚拟环境 env。这个计算阶乘的程序如下:

A = r'''
B = "A = r\'''" + A + "\'''\n" + A
n = 10
if n == 1:
    ans = 1
else:
    B = B.replace('n = '+str(n),'n = '+str(n-1),2)
    env = {}
    exec(B,env)
    ans = n * env['ans']
print ans
'''
B = "A = r\'''" + A + "\'''\n" + A
n = 10
if n == 1:
    ans = 1
else:
    B = B.replace('n = '+str(n),'n = '+str(n-1),2)
    env = {}
    exec(B,env)
    ans = n * env['ans']
print ans

其实在我想出来虚拟一个环境之前,我是实现的下面这个代码。和上面不同的是,由于修改了当前变量,所以无法保存之前的状态(比如 n)。咦?!这不就是尾递归吗?所以就按照尾递归的思路实现了,把 ans 当做变量传下去,如果你做过 SICP 的话,对这种写法应该不陌生。

A = r'''
B = "A = r\'''" + A + "\'''\n" + A
ans = 1
n = 10
if n > 1:
    B = B.replace('ans = '+str(ans),'ans = '+str(ans*n),2)
    B = B.replace('n = '+str(n),'n = '+str(n-1),2)
    exec(B)
print ans
'''
B = "A = r\'''" + A + "\'''\n" + A
ans = 1
n = 10
if n > 1:
    B = B.replace('ans = '+str(ans),'ans = '+str(ans*n),2)
    B = B.replace('n = '+str(n),'n = '+str(n-1),2)
    exec(B)
print ans

不知道看完本文的你是感到有些蛋疼菊紧呢,还是感到仿佛触碰到了计算机科学的灵魂……

PS: 本文奇葩代码貌似可秒杀多数代码高亮程序,包括 vim,iPython 和本 blog 用的 SyntaxHighlighter,前两者只有一点儿错,可以拷进去看。

from scturtle's 渣代码集散地: http://scturtle.is-programmer.com/posts/34225

Written by cwyalpha

六月 17, 2012 在 5:38 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: