专栏首页窗户相互递归(2)

相互递归(2)

  版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址

  http://www.cnblogs.com/Colin-Cai/p/10920847.html 

  作者:窗户

  QQ/微信:6679072

  E-mail:6679072@qq.com

  本章继续上一章,说明一下这个问题:

  所有的相互递归都可以被转化为一般的递归,从而最终可以用lambda演算来完成。

  假设有以下对于f_1,f_2, ... f_n 的相互递归:

  f_{1} = F_{1}(f_{1}, f_{2}, ... f_{n})

  f_{2} = F_{2}(f_{1}, f_{2}, ... f_{n})

  ...

  f_{n} = F_{n}(f_{1}, f_{2}, ... f_{n})

  如果我们定义一个高阶函数(算子)f,满足

  f_{1} = f(1)

  f_{2} = f(2)

  ...

  f_{n} = f(n)

  代入上式,得到

  f(1) = F_{1}(f(1), f(2), ... f(n))

  f(2) = F_{2}(f(1), f(2), ... f(n))

  ...

  f(n) = F_{n}(f(1), f(2), ... f(n))

  于是以上就是一个对于f的普通递归(f递归到f)。

  从而,我们就知道了,任何递归都可以转化为到自身的普通递归

  然而,对于lambda演算,因为自身没有名字,那又如何递归呢?

  我们就用非负整数的最大公约数为例子,还是用Scheme,一步步来。

  我们记gcd(a_1,a_2, ..., a_n)a_1,a_2, ..., a_n的最大公约数。

  最大公约数的递归其实很简单:

  (1)gcd(0, a) = a

  (2)如果a不等于0,那么 gcd(a, b) = gcd(b\%a, a),此处%是取余数

  (3)gcd(a_1, a_2, ... a_n) = gcd(a_1, gcd(a_2, ... a_n))

  其中第一条、第二条连续使用就是著名的欧几里得算法,或者称辗转相除法。

  而第三条则用于缩减最大公约数求解的个数,之前我在文章《汉诺塔——各种编程范式的解决》提到,递归可求解的真谛在于缩小问题处理的规模以达到降阶,以上第二、三条则是可以达到降阶的效果。

  于是上述三条再加上gcd() = 0gcd(0) = 0 这两条边界条件,用Scheme描述递归如下:

(define gcd
 (lambda s
  (if (null? s)
   0
   (if (zero? (car s))
    (apply gcd (cdr s))
    (if (null? (cdr s))
     (car s)
     (if (null? (cddr s))
      (gcd (remainder (cadr s) (car s)) (car s))
      (gcd (car s) (apply gcd (cdr s)))
     ))))))

  为了实现匿名递归,也就是我们最终希望在lambda演算中递归,我们需要考虑以下函数

(define g
 (lambda (f)
  (lambda s
   (if (null? s)
    0
    (if (zero? (car s))
     (apply f (cdr s))
     (if (null? (cdr s))
      (car s)
      (if (null? (cddr s))
       (f (remainder (cadr s) (car s)) (car s))
       (f (car s) (apply f (cdr s)))
      )))))))

  我们此处好好想一想,会发现,g(gcd) = gcd

  也就是gcd是函数g的不动点。

  其实不动点在其他函数中一样存在,比如f(x) = x的不动点是0,

  只是这里的函数是高阶函数(算子),似乎挺拗口。

  假如有个函数Y(当然,这个Y也是一个算子)可以找到算子的不动点,比如使得$g(Y(g)) = Y(g)$,那么Y(g)就是我们本来想要实现的gcd,

  于是我们就通过lambda演算实现了匿名递归。

  那么这样的Y存在吗?

  幸运的是,Y函数是存在的,有个学名叫Y combinator,我们知道美国有个孵化器公司叫这个名字,实际上就是取这个的意义。这个早在Church创建lambda验算体系的时候就已经发现,而且至关重要,否则就不知道怎么递归了。

  Scheme下,Y combinator可以如下

(lambda (f)
 ((lambda (g) (g g))
  (lambda (x) (f (lambda s (apply (x x) s))))))

  因为gcd函数可以表示为Y(g)的形式,

  于是,我们的gcd就可以形式如下

(define gcd
 ((lambda (f)
   ((lambda (g) (g g))
    (lambda (x) (f (lambda s (apply (x x) s))))))
  (lambda (f)
   (lambda s
    (if (null? s)
     0
     (if (zero? (car s))
      (apply f (cdr s))
      (if (null? (cdr s))
       (car s)
       (if (null? (cddr s))
        (f (remainder (cadr s) (car s)) (car s))
        (f (car s) (apply f (cdr s)))
       ))))))))

  于是,我们发现gcd的定义过程中,只用到了lambda演算,从而lambda演算统一了一切!

  靠谱吗?那么我们用上述定义的如此诡异的gcd随便运算一下几组最大公约数

(display (gcd 225 150 165))

  得到

15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Scheme实现数字电路仿真(1)——组合电路

      EDA是个很大的话题,本系列只针对其中一小部分,数字电路的仿真,叙述一点概念性的东西,并不会过于深入,这方面的内容实则是无底洞。本系列并不是真的要做EDA,...

    窗户
  • 相互递归(3)

      我们根据上一章最开始的相互递归转一般递归的方法,结合Y Combinator,来对第一章的append实现做一下测试。

    窗户
  • 我博客上的围棋js程序

      版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址   http://www.cnblogs.com/Colin-C...

    窗户
  • 中国加快基于 IPv6 的互联网发展,2025 年实现全覆盖

    中共中央办公厅、国务院办公厅印发了《推进互联网协议第六版(IPv6)规模部署行动计划》,计划全面推进部署 IPv6,协同推进网络实名制。

    Debian中国
  • 百度有戏:不好意思,大数据这次搞错了。

    ? 百度最近应该比较郁闷,因为国庆假期前高调上线的“百发有戏”押错了宝,被寄予厚望的《黄金时代》国庆黄金档票房收入仅3100余万元,不仅远远落后于同期上映的《...

    小莹莹
  • 全球43亿个IPv4地址正式耗尽,IPv6时代即将到来,中国取得了哪些骄傲的成就?

    IPv4,是互联网协议的第四版(Internet Protocol Version 4 ),IPv4地址就是我们日常说的ip地址,比如常见的192.168.1....

    网络技术联盟站
  • AI 能预测夫妻吵架,还会劝你冷静一下

    场景描述:夫妻、伴侣之间,吵架几乎是不可避免的。争吵时的情绪失控,常常会对双方都造成伤害,甚至导致昔日的爱人最终分道扬镳。而现在,AI 已经学会了察言观色,帮助...

    HyperAI超神经
  • 全球 43 亿个 IPv4 地址已正式耗尽,未来我们该怎么办呢?

    该消息是在一封电子邮件(由 Nikolas Pediaditis 发布)中宣布的,内容为:

    iMike
  • 提升iOS审核通过率之“IPv6兼容测试”

    在WWDC2015大会上苹果宣布iOS9将支持纯IPv6的网络服务。2016年6月1号,所有提交到AppStore上的应用都必须支持IPv6,否则将通不过审核。...

    WeTest质量开放平台团队
  • 互联网再升级,蓝汛CEO谈IPv6发展历程

    IPv6是Internet Protocol Version 6的缩写,是互联网工程任务组设计的用于替代现行IPv4的下一代IP协议,号称可以为全世界的每一粒沙...

    用户5797785

扫码关注云+社区

领取腾讯云代金券