资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/如何实现一个没有名字的递归函数

如何实现一个没有名字的递归函数

tinna / 651人阅读

摘要：如果存在这么个函数，那么我们就可以通过求解的不动点来求出了。寻找转换函数的不动点找到了转换函数后，下一步就是确定其不动点了，而这个不动点就是我们最终想要的。

本文原发于个人博客

递归 作为计算机科学中很重要的一个概念，应用范围非常广泛。比较重要的数据结构，像树、图，本身就是递归定义的。
比较常见的递归算法有阶乘、斐波那契数等，它们都是在定义函数的同时又引用本身，对于初学者来说也比较好理解，但是如果你对编程语言，特别是函数式语言，有所研究，可能就会有下面的疑问：

一个函数在还没有定义完整时，为什么能够直接调用的呢？

这篇文章主要是解答上面这个问题。阅读下面的内容，你需要有些函数式编程的经验，为了保证你能够比较愉快的阅读本文，你至少能看懂前缀表达式。相信读完本文后，你将会对编程语言有一全新的认识。
本文所有演示代码有Scheme、JS两个版本。

问题描述

下面的讲解以阶乘为例子：

; Scheme
(define (FACT n)
  (if (= n 0)
    1
    (* n (FACT (- n 1)))))

; JS
var FACT = function(n) {
    if (n == 0) {
        return 1;
    } else {
        return n * FACT(n-1);
    }
}

上面的阶乘算法比较直观，这里就不再进行解释了。重申下我们要探究的问题

FACT 这个函数为什么在没有被定义完整时，就可以调用了。
问题分析

解决一个新问题，常见的做法就是类比之前解决的问题。我们要解决的这个问题和求解下面的等式很类似：

2x = x + 1

在等号两边都出现了x，要想解决这个问题，最简单的方式就是将等号右边的x移到左边即可。这样就知道x是什么值了。

但是我们的问题比这个要复杂些了，因为我们这里需要用if、n、*、-这四个符号来表示FACT，可以这么类比是因为一个程序无非就是通过一些具有特定语意的符号（编程语言规定）构成的。

再进一步思考，FACT 需要用四个符号来表示，这和我们求解多元方程组的解不是很像嘛：

x + y = 3
x - y = 1

为了求解上面方程组，一般可以转为下面的形式：

x = 3 - y
y = x - 1

即

(x, y) = T (x, y)

其中的T为一个转换，在线性代数其实就是个矩阵，根据矩阵T的一些性质，我们可以判定(x ,y)是否有解，以及解的个数。

对比此，我们可以把问题转化为下面的形式：

FACT = F (FACT)

上面的F为某种转换，在这里其实就是个需要一个函数作为参数并且返回一个函数的函数。如果存在这么个F函数，那么我们就可以通过求解F的不动点来求出FACT了。

但这里有个问题，即便我们知道了F的存在，我们也无法确定其是否存在不动点，以及如果存在，不动点的个数又是多少？

计算机科学并不像数学领域有那么多可以套用的定理。

寻找转换函数 F

证明F是否存在是个比较难的问题，不在本文的讨论范围内，这涉及到Denotational semantics领域的知识，感兴趣的读者可以自己去网上查找相关资料。

这里直接给出FACT对应的函数F的定义：

; Scheme
(define F
  (lambda (g)
    (lambda (n)
      (if (= n 0)
        1
        (* n (g (- n 1)))))))

; JS
var F = function(g) {
    return function(n) {
        if (n == 0) {
            return 1;
        } else {
            return x * g(n-1);
        }
  }
}

可以看到，对比递归版本的FACT变动不大，就是把函数内FACT的调用换成了参数g而已，其实我们常见的递归算法都可以这么做。

寻找转换函数 F 的不动点

找到了转换函数F后，下一步就是确定其不动点了，而这个不动点就是我们最终想要的FACT。

FACT = (F (F (F ...... (F FACT) ...... )))

假设我们已经知道了FACT非递归版本了，记为g，那么

E0 = (F g)      这时(E0 0) 对应 (FACT 0)得值，这时用不到 g
E1 = (F E0)     这时(E1 0)、(E1 1)分别对应(FACT 0)、(FACT 1)的值
E2 = (F E1)     这时(E2 0)、(E2 1)、(E2 2)分别对应(FACT 0)、(FACT 1)、(FACT 2)的值
.....
En = (F En-1)   这时....(En n)分别对应.... (FACT n)的值

可以看到，我们在求出(FACT n)时完全没有用到初始的g，换句话说就是g的取值不影响我们计算(FACT n)。
那么我们完全可以这么定义FACT：

FACT = (F (F (F ...... (F 1) ...... )))

可惜，我们不能这么写，我们必须想个办法表示无穷。在函数式编程中，最简单的无穷循环是：

; Scheme
((lambda (x) (x x))
  (lambda (x) (x x)))

; JS
(function (x) {
    return x(x);
})(function(x) {
    return x(x);
});

基于此，我们就得到函数式编程中一重要概念 Y 算子，关于 Y 算子的严格推导，可以在参考这篇文章 The Y combinator (Slight Return)，这里直接给出：

; Scheme
(define Y
  (lambda (f)
    ((lambda (x) (f (x x))
      (lambda (x) (f (x x)))))))

(define FACT (Y F))

; JS
var Y = function(f) {
    return (function(x) {
        return f(x(x));
    })(function(x) {
        return f(x(x));
    });
}
var FACT = Y(F);

这样我们就得到的FACT了，但这里得到的FACT并不能在Scheme或JS解释器中运行，因为就像上面说的，这其实是个死循环，如果你把上面代码拷贝到解释器中运行，一般可以得到下面的错：

RangeError: Maximum call stack size exceeded
正则序 vs. 应用序

为了得到能够在Scheme或JS解释器中可以运行的代码，这里需要解释复合函数在调用时传入参数的两种求值策略：

正则序（Normal Order），完全展开而后归约求值。惰性求值的语言采用这种顺序。

应用序（Applicative Order），先对参数求值而后应用。我们常用的大部分语言都采用应用序。

举个简单的例子：

var p = function() {
    return (p);
}
var test = function(x, y) {
    if(x == 0) {
        return 0;
    } else {
        return y;
    }
}
test(0, (p));

上面这个例子，采用应用序的语言会产生死循环；而采用正则序的语言可以正常返回0，因为test的第二个参数只有在x不等于0时才会去求值。

我们上面给出的var FACT = Y(F)在正则序的语言中是可行的，因为Y(F)中的返回值只有在真正需要时才进行求值，而在F中，n等于0时是不需要对g(n-1)进行求值的，所以这时Y(F)(5)就能够正常返回120了。

如果你觉得上面这段话很绕，一时不能理解，这样很正常，我也是花了很久才弄明白，你可以多找些惰性求值的文章看看。

为了能够得出在应用序语言可用的FACT，我们需要对上面的Y做进一步处理。思路也很简单，为了不立即求值表达式，我们可以在其外部包一层函数，假设这里有个表达式p：

var lazy_p = function() { return p; }

这时如果想得到p的值，就需要(lazy_p)才可以得到了。基于这个原理，下面给出最终版本的Y 算子：

; Scheme
(define Y
  (lambda (f)
    ((lambda (x) (x x))
     (lambda (x) (f (lambda (y) ((x x) y)))))))

(define FACT (Y F))
(FACT 5)   ;===> 120

; JS
 var Y = function(f) {
     return function(x) {
         return x(x)
     }(function (x) {
         return f(function(y) {
             return x(x)(y)
         })
     })
 }
 var FACT = Y(F)
 FACT(5)   ;===> 120

好了，到现在为止，我们已经得到了可以在Scheme或JS解释器中运行FACT了，可以看到，这里面没有使用函数名也实现了递归方式求阶乘。
本文一开始给出的FACT版本在解释器内部也会转换为这种形式，这也就解释了本文所提出的问题。

总结

本文大部分内容由 SICP 4.1 小节延伸而来，写的相对比较粗糙，很多点都没有展开讲的原因是我自己也还没理解透彻，为了不误导大家，所以这里就省略了（后面理解的更深刻后再来填坑?）。希望感兴趣的读者能够自己去搜索相应知识点，相信肯定会受益匪浅。

最后，希望这篇文章对大家理解编程语言有一些帮助。有什么不对的地方请留言指出。

GPU云服务器 云服务器 迷你世界云服务器没有名字的人 js如何清除一个函数 递归函数printf 递归函数python

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/78729.html

相关文章

  • 关于javascript函数式编程中compose的实现

    摘要：结论这次主要介绍了函数式编程中的函数的原理和实现方法，由于篇幅原因，我把打算分析的源码实现放到下一篇来介绍，可以说实现的更加函数式，需要单独好好分析。 上一篇文章介绍了javascript函数式编程中curry（柯里化）的实现，当然那个柯里化是有限参数的柯里化，等有机会在补上无限参数的那一种柯里化，这次主要说的是javascript函数式编程中另外一个很重要的函数compose，com...

    jonh_felix 评论0 收藏0

  • 【数据科学系统学习】Python # 编程基础[一]

    摘要：在定义函数时给定的名称称作形参，在调用函数时你所提供给函数的值称作实参。调用函数要调用一个函数，需要知道函数的名称和参数。默认参数值可以有效帮助解决这一情况。是默认参数定义默认参数要牢记一点默认参数必须指向不变对象。 关于数据科学在做什么，我们已经在前两篇文章中进行了总结，即专题概述和描述性统计分析。要进行数据科学的探索，需要一个好工具，就是Python。从本篇开始，将总结学习Pyth...

    luckyyulin 评论0 收藏0

  • Python基础教程

    摘要：函数内的变量被称为局部变量，这是与全局变量相反的概念。有一些进行函数式编程的机制。继承以通用的类为基础建立专门的类对象。 6.4.5 参数收集的逆过程 假设有如下函数： def add(x,y): return x+y 比如说有个包含由两个相加的数字组成的元组： params = (1,2) 使用*运算符对参数进行分配，不过是在调用而不是在定义时使用： >>> add(*params)...

    daydream 评论0 收藏0

  • JS学习笔记（第7章）（函数表达式）

    摘要：递归闭包模仿块级作用域私有变量小结在编程中，使用函数表达式可以无需对函数命名，从而实现动态编程。匿名函数也称为拉姆达函数。函数声明要求有名字，但函数表达式不需要。中的函数表达式和闭包都是极其有用的特性，利用它们可以实现很多功能。 1、递归 2、闭包 3、模仿块级作用域 4、私有变量 5、小结 在JavaScript编程中，使用函数表达式可以无需对函数命名，从而实现动态编程。匿名函数也称...

    xiaokai 评论0 收藏0

  • 如何读懂并写出装逼的函数式代码

    摘要：如下所示这个是不是有点作弊的嫌疑，我们再往下，把上面这个函数整成箭头函数式的匿名函数的样子。动用高阶函数的递归但是上面这个递归的匿名函数在自己调用自己，所以，代码中有的实参。 今天在微博上看到了 有人分享了下面的这段函数式代码，我把代码贴到下面，不过我对原来的代码略有改动，对于函数式的版本，咋一看，的确令人非常费解，仔细看一下，你可能就晕掉了，似乎完全就是天书，看上去非常装逼，哈哈。不...

    刘明 评论0 收藏0

发表评论

登陆后可评论

0条评论

tinna

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<