匿名递归

 
先贴上 Homework 3 Recursion, Tree Recursion 中的最后一道思考题题面：

This question demonstrates that it's possible to write recursive functions without assigning them a name in the global frame.

The recursive factorial function can be written as a single expression by using a conditional expression.

>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
>>> fact(5)
120

However, this implementation relies on the fact (no pun intended) that fact has a name, to which we refer in the body of fact. To write a recursive function, we have always given it a name using a def or assignment statement so that we can refer to the function within its own body. In this question, your job is to define fact recursively without giving it a name!

Write an expression that computes n factorial using only call expressions, conditional expressions, and lambda expressions (no assignment or def statements).

Note: You are not allowed to use make_anonymous_factorial in your return expression.

The sub and mul functions from the operator module are the only built-in functions required to solve this problem.

def make_anonymous_factorial():

    """Return the value of an expression that computes factorial.

    >>> make_anonymous_factorial()(5)

    120

    >>> from construct_check import check

    >>> # ban any assignments or recursion

    >>> check(HW_SOURCE_FILE, 'make_anonymous_factorial',

    ...     ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'FunctionDef', 'Recursion'])

    True

    """

    return 'YOUR_EXPRESSION_HERE'

 

答案代码

def make_anonymous_factorial():
    return (lambda f: lambda k: f(f, k))(lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1))))

 

思路

我们以

fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))

作为基础进行修改

题目要求不能使用赋值和 def 定义，这意味着不能在全局框架中增加新的函数绑定，然而，必须使用递归实现，这意味着必须在函数中调用自身——如果要进行函数调用，则必须使用函数的名称，这是不可避免的。

通过上述分析，可以知道，为了在递归调用时能够指称函数，我们不得不使用由 lambda 函数绑定的形式参数，因此，一个基本的框架是：

lambda f: ...

这样一来，就能通过名称 f 来递归调用了！

让我们把这个框架与原先的基础代码（随意地，漫无目的地）结合起来：

lambda f: lambda n: 1 if n == 1 else mul(n, f(sub(n, 1)))

现在，这个表达式起到的作用是接受一个函数 f ，转换成这样一个函数：如果参数是 1 ，则输出 1，否则输出 n * f (n - 1)

然而，这和目标有着很大的差距！如果要直接使用这个匿名高阶函数，将它应用于一个函数 h，这显然是不可行的：假设可行，由于 h 以一个整数 n 作为唯一参数， 且返回一个整数，我们会发现这个匿名高阶函数并未将其转化为一个递归过程，而是最多将 h(3) 转换为 h(2) 就停止了

我们考虑一个关于信息的小问题：可以观察到，我们辛辛苦苦用 lambda 函数绑定的名称 f， 在“递归”一次后就丢失了，那么显然不能继续递归了

如何不让这一信息丢失？当然是把这一信息作为参数代代相传！

因此，我们把 f 修改为一个双参数函数，多出来的一个参数是 f 本身，对代码略作修改（事实上，有两处地方需要同时修改）：

lambda f: lambda f, n: 1 if n == 1 else mul(n, f(f, sub(n, 1)))

由于已经有了 lambda f, n:，不再需要 lambda f:来绑定名称了，所以核心缩减为：

lambda f, n: 1 if n == 1 else mul(n, f(f, sub(n, 1)))

几乎快完成了！能够惊喜地发现，在解决信息传递问题的同时，顺带着也实现了递归！设想我们计算 f (f, 5)，结果是 5 * f (f, 4)，也就是 5 * 4 * f (f, 3) ... 这就成功了。

唯一的问题是：这个过程没办法开始，如果要这样开始第一次计算，就需要传入参数 f, n，而 f 此时还没有定义。

考虑希望达到的效果：输入 n， 输出 n 的阶乘。我们必须把输入缩减到一个变量，这既是为了避免计算过程无法开始的困难，也是业务本身的要求，因此，我们通过一个高阶函数来构造一个计算的入口：

(lambda f: lambda k: f(f, k))

将这个入口应用于核心函数：

(lambda f: lambda k: f(f, k))(lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1))))

这就完成了整道题目