不定义函数实现递归（python）

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

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

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

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

得到程序自身后，当然需要再次运行它，我们利用 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 和本站用的 SyntaxHighlighter，前两者只有一点儿错，可以拷进去看。