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

相互递归(1)

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

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

  作者:窗户

  QQ/微信:6679072

  E-mail:6679072@qq.com

  相互递归就是多个函数互相定义,最常见的就是两个函数,比如f和g,f的定义中用到g,而g的定义中用到f。

  相互递归一样有无限递归的可能,最简单的:

  f:x->g(x)

  g:x->f(x)

  给个最简单的没有无限递归的例子,判断一个正整数是不是偶数或者是不是奇数,用C++来描述如下:

bool is_odd(unsigned x);
bool is_even(unsigned x)
{
        if(x == 0u)
                return true;
        return is_odd(x-1u);
}
bool is_odd(unsigned x)
{
        if(x == 0u)
                return false;
        return is_even(x-1u);
}

  以上效率虽然不高(甚至不优化的情况下,可能会崩栈),但是is_even和is_odd两个函数毕竟是相互定义的,也是相互递归的一个经典例子。

  Scheme当然一样支持相互递归,r5rs中也是以上述奇偶来做例子。

(define (even? x)
 (if (zero? x)
  #t
  (odd? (- x 1))
 )
)
(define (odd? x)
 (if (zero? x)
  #f
  (even? (- x 1))
 )
)

  再给个稍微复杂的例子,Scheme里的append是个常用的函数,它可以传入一组列表,得到这组列表首尾拼接在一起的列表。比如:(append '(1 2 3) '(4 5 6) '(7 8 9))得到(1 2 3 4 5 6 7 8 9)。

  每个人学习Scheme的过程,基本必然伴随着append函数的自我实现。

  以下是其中一种实现(当然,append有好几种不同的实现思想):

(define (append . lst)
 (if (null? lst)
  '()
  ((apply _append (cdr lst)) (car lst))
 )
)

(define (_append . lst)
 (cond
  ((null? lst) (lambda (x) x))
  ((null? (cdr lst))
   (lambda (x)
    (if (null? x)
     (car lst)
     (cons (car x) ((_append (car lst)) (cdr x)))
    )
   )
  )
  (else (_append (apply append lst)))
 )
)

  当然,_append一般应该实现在append的内部,我这么写也是为了表示的清楚一点。这种写法是一种相对高级一点的写法,采用的算子方式,不断用闭包来传递信息,并使用了相互递归,append和_append两个函数互相定义。

  当然,一开始就说了,相互递归完全可以不只是两个函数之间的关系,可以是多个函数之间的关系。

  我这里给个例子,把正整数按照除以3得到的余数分为三类,把整除3的数称为type0,把除以3余1的数称为type1,把除以3余2的数称为type2。于是定义三个谓词函数type0? type1? type2?

  以下为实现:

(define (type0? x)
 (if (= x 0)
  #t
  (type2? (- x 1))
 )
)
(define (type1? x)
 (if (= x 0)
  #f
  (type0? (- x 1))
 )
)
(define (type2? x)
 (if (= x 0)
  #f
  (type1? (- x 1))
 )
)

  我们可以看到,

  type0?的定义中用到type2?

  type1?的定义中用到type0?

  type2?的定义中用到type1?

  测试一下,

(for-each
 (lambda (x) (display x)(newline))
 (map
  (lambda (x)
   (cons
    x
    (map (lambda (f) (f x)) (list type0? type1? type2?))
   )
  )
  (range 20)
 )
)

  得到

(0 #t #f #f) (1 #f #t #f) (2 #f #f #t) (3 #t #f #f) (4 #f #t #f) (5 #f #f #t) (6 #t #f #f) (7 #f #t #f) (8 #f #f #t) (9 #t #f #f) (10 #f #t #f) (11 #f #f #t) (12 #t #f #f) (13 #f #t #f) (14 #f #f #t) (15 #t #f #f) (16 #f #t #f) (17 #f #f #t) (18 #t #f #f) (19 #f #t #f)

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 相互递归(3)

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

    窗户
  • 古中国数学家的计算力真是惊人

      现代数学是建立在公理化的体系之上,可以认为是形而上学。公理化是数学的本质所在,古代中国人建立过数学的辉煌,但是却似乎并没有去思考数学的本质,而古希腊的《几何...

    窗户
  • 平方根的C语言实现(三) ——最终程序实现

      了解了浮点数的存储以及手算平方根的原理,我们可以考虑程序实现了。   先实现一个64位整数的平方根,根据之前的手算平方根,程序也不是那么难写了。 #incl...

    窗户
  • SpringBoot中spring.jackson.date-format配置失效的解决办法

    如果发现spring.jackson.date-format失效,是因为mvc配置中加入了如下注解:

    飞奔去旅行
  • 新合作帮助英国新创企业获取超级计算AI资源

    英国Digital Catapult公司和超级计算厂商Cray开展的一项合作将帮助新创公司获取Cray公司人工智能实验室的超级计算资源。

    人工智能快报
  • Android检测当前屏幕的方向

    做为一个不那么像初学者的初学者,我注意到Android已经提供了检测屏幕方向的API,而我在《Android 4编程入门经典——开发智能手机与平板电脑应用》书中...

    用户3579639
  • Android LayoutInflater.inflate()源码流程分析

      我们在根据layout文件得到View的时候都会使用LayoutInflater.from(mContext).inflate().下面我们来分析这个获取V...

    曾大稳
  • 【一天一大 lee】有序数组的平方 (难度:简单) - Day20201016

    给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。

    前端小书童
  • Go | 字符串拼接的总结和分析

    在 test 包中新建 str_append_test.go 文件,并在其中编写 Benchmark 测试代码,如下:

    CnPeng
  • Xshell如何添加快捷命令的方法

    作为好用的终端模拟器,Xshell经常被开发者用来远程管理主机服务器,为了更加高效地进行操作,我们可以添加一些快捷命令,从而运用命令来操作。

    砸漏

扫码关注云+社区

领取腾讯云代金券