同余式的加减乘除

不定义函数实现递归(python)

scturtle posted @ 2012年6月17日 10:15 in algorithm , 4253 阅读

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

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,前两者只有一点儿错,可以拷进去看。

Avatar_small
Plux 说:
2012年6月17日 16:51

exec()不相当于读取源文件吗?

Avatar_small
scturtle 说:
2012年6月17日 20:32

得到自身代码是在exec之前,exec只是起到了一个可以运行任何图灵机的通用图灵机的作用,这也是py能做到文中程序的主要原因

Avatar_small
Plux 说:
2012年6月18日 11:02

那其实和函数递归差不多吧。。。

Avatar_small
scturtle 说:
2012年6月18日 11:56

可在函数递归里, 获得函数自身代码是在函数定义里调用自身时语言隐式完成的啊, 否则为何要费劲实现第一个程序呢

skip 说:
2012年11月27日 14:50

这个~~~~

太绕了~~~~~


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter