hi,你好!欢迎访问本站!登录
本站由网站地图腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

种种编程语言对尾递归的支撑

2019-11-18杂谈搜奇网55°c
A+ A-
  版权说明:本文为博主窗户(Colin Cai)原创,迎接转帖。如要转贴,必需说明原文网址

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

  作者:窗户

  QQ/微信:6679072

  E-mail:6679072@qq.com

  尾递归

 

  这篇文章,我们讲尾递归。在递归中,假如该函数的递归情势表如今函数返回的时刻,则称之为尾递归。

  举个简朴的例子,用伪码以下:

  function Add(a, b)

  if a = 0

    return b

  return Add(a-1, b+1)

  end

  

  上面这个函数实际上是两个数的加法,简朴起见,只斟酌非负整数,背面叙说详细言语总是会以这个函数为例子。一切的return部份都是不再依赖于递归,或许是返回Add函数,其参数的盘算不再依赖于递归,典范的尾递归。

  上述代码很容易用轮回示意:

  

  function Add(a, b)

  while True

    if a = 0

      return b

    end

    a <= a-1

    b <= b+1

  end

  end

 

  一切的尾递归都能够用轮回示意,只须要把传入的参数当做是状况,运算的历程当做是状况的转换。

  比方Add(3,0)的盘算就经由

  3,0

  2,1

  1,2

  0,3

  如许的状况转换。

  

  函数的盘算会保护一个栈,每当碰到函数挪用会纪录当前运转的状况,云云在函数返回的时刻能够恢复上下文。

  比方,关于Fibonacci数列,伪码以下:

 

  function fib(n)

  if n < 3

    return 1

  end

  return fib(n-1)+fib(n-2)

  end

  

  我们盘算fib(4),栈大抵以下:

  fib(4)

  =>

  fib(4)

  fib(3)

  =>

  fib(4)

  fib(3)

  fib(2)

  =>

  fib(4)

  fib(3)

  fib(2) 1

  =>

  f(4)

  f(3) 1+

  =>

  f(4)

  f(3) 1+

  f(1)

  =>

  f(4)

  f(3) 1+

  f(1) 1

  =>

  f(4)

  f(3) 2

  =>

  f(4) 2+

  =>

  f(4) 2+

  f(2)

  =>

  f(4) 2+

  f(2) 1

  =>

  f(4) 3

  =>

  3

  

  而作为尾递归,我们盘算Add(3,0),栈多是以下历程:

  Add(3,0)

  =>

  Add(3,0)

  Add(2,1)

  =>

  Add(3,0)

  Add(2,1)

  Add(1,2)

  =>

  Add(3,0)

  Add(2,1)

  Add(1,2)

  Add(0,3)

  =>

  Add(3,0)

  Add(2,1)

  Add(1,2)

  Add(0,3) 3

  =>

  Add(3,0)

  Add(2,1)

  Add(1,2) 3

  =>

  Add(3,0)

  Add(2,1) 3

  =>

  Add(3,0) 3

  =>

  3

 

  关于Add函数,以上栈的长度与盘算量成正比。云云,意味着盘算量越大所须要的栈越大,以至致使凌驾最大限定而没法运算。

  同时我们发明,简朴的转为轮回示意的Add则没有这个题目。

  这里,能够采纳一个编译手艺,就是尾递归优化,其平常状况是,假如一个函数的盘算中碰到了完整转化成另一个函数挪用的状况,那末栈的当前函数部份的信息能够完整抹去,而替换为新的函数。云云处置惩罚下,此状况栈不会增进。

  Add(3,0)的栈的历程以下:

  Add(3,0)

  =>

  Add(2,1)

  =>

  Add(1,2)

  =>

  Add(0,3)

  =>

  3

 

  尾递归优化给了我们一种迭代的体式格局,之所以研讨它,在于函数式编程会用到它。

  注:递归论辨别递归和迭代(迭置),和盘算机上定义有一点区分,在此不深切。

 

C/C++

 

  我们从底层的言语最先,起首照样上面的加法完成。为了让局限更大一点,便于视察,我们运用unsigned long long范例。

/*add.c*/
unsigned long long add(unsigned long long a, unsigned long long b)
{
        if(a==0ULL)
                return b;
        return add(a-1ULL,b+1ULL);
}

  再写一个main来测试它,用命令行参数去取得传入add的两个参数

#include <stdio.h>
unsigned long long add(unsigned long long a, unsigned long long b);
int main(int argc, char **argv)
{
    unsigned long long a, b;
    sscanf(argv[1], "%llu", &a);
    sscanf(argv[2], "%llu", &b);
    printf("%llu\n", add(a,b));
    return 0;
}

  用gcc编译,

  gcc add.c main.c -o a.out

  运转一下,

  ./a.out 10000000 100000000

  立时发作短毛病,直接崩溃。看来C言语作为底层言语没必要支撑这个啊?

  因而我们开启优化,

  gcc -O2 add.c main.c -o a.out

  然后运转一下

  ./a.out 10000000000000000 10000000000000000

  马上获得我们想要的值而没有发作崩栈

  20000000000000000

  看来……不对,1亿亿次迭代霎时完成?

  objdump反汇编一把,

00000000004006b0 <add>:
  4006b0:       48 8d 04 37             lea    (%rdi,%rsi,1),%rax
  4006b4:       c3                      retq   

  ……本来全被优化了,gcc如今还真壮大,直接猜出语义,clang测一把也是云云。

  这个并不是我们想要的,我们得用其他手腕去考证(实在我们能够抽出部份优化选项来,但此处讲的是考证思绪)。

  此处借助我在《互相递归》中讲的奇偶推断,分三个函数,完成以下,

/*sub1.c*/
unsigned long long sub1(unsigned long long x)
{
        return x - 1ULL;
}
/*is_odd.c*/
unsigned long long sub1(unsigned long long x);
int is_even(unsigned long long x);
int is_odd(unsigned long long x)
{
        if(x == 0ULL)
                return 0;
        return is_even(sub1(x));
}
/*is_even.c*/
unsigned long long sub1(unsigned long long x);
int is_odd(unsigned long long x);
int is_even(unsigned long long x)
{
        if(x == 0ULL)
                return 1;
        return is_odd(sub1(x));
}

  上述函数是零丁编写,以至,减1的操纵也零丁用一个文件来完成。云云测试的缘由,就在于,我们要排撤除团体优化的能够。

  还须要写一个main函数来考证,

/*main.c*/
#include <stdio.h>
int is_odd(unsigned long long x);
int main(int argc, char **argv)
{
    unsigned long long x;
    sscanf(argv[1], "%llu", &x);
    printf("%llu is %s\n", x, is_odd(x)?"odd":"even");
    return 0;
}

  以上四个文件零丁编译,开启-O2优化选项(固然,实在main无所谓)

  for i in sub1.c is_odd.c is_even.c main.c; do gcc -O2 -c $i; done

  然后链接,

  gcc sub1.o is_odd.o is_even.o main.o -o a.out

  然后我们对一个很大的数来举行测试,

  ./a.out 10000000000

  一会儿以后,顺序打印出

  10000000000 is even

  以上能够证实,gcc/clang关于尾递归优化支撑的挺好。实际上,很早之前大部份C言语编译器就支撑了这点,由于从手艺上来看,并不是很庞杂的事变。而C++也同理。

 

Python

 

  Python完成add以下

def add(a, b):
    if a==0:
        return b
    return add(a-1, b+1)

  盘算add(1000,0)就崩栈了,明显Python的刊行是不支撑尾递归优化的。

  不过这里栈好像小了点,能够用sys.setrlimit来修正栈的大小,这实际上是UNIX-like的体系挪用。

  有人用捕获非常的体式格局让其强行支撑尾递归,效力固然是丧失许多的,不过这个主意却是很好。想起之前RISC大多不支撑奇边境存取值,比方ARM,因而在内核顶用中断处置惩罚强行支撑奇边境毛病,虽然效力低了许多,但逻辑上是经由过程的。殊途同归,确实也是一条路,不过我照样越发希冀Python在将来支撑尾递归优化吧。  

 

JavaScript

 

  依然是用add测试,编写以下网页

<input type="text" id="in1" />
<input type="text" id="in2" />
<input type="button" id="bt1" onclick="test()" value="测试"/>
<script type="text/javascript">
function add(a, b)
{
    if (a==0) { 
        return b;
    }
    return add(a-1, b+1);
}

function test()
{
    a = parseInt(document.getElementById("in1").value);
    b = parseInt(document.getElementById("in2").value);
    try {
        alert(add(a,b));
    }
    catch(err) {
        alert('Error');
    }
}
</script>

 

  

  就用1000000和0来测试,没看到哪一个浏览器不跳出Error的……听说v8引擎做好了,然则人家就不给你用……

 

 

Scheme

 

  然后我们来看Scheme,根据Scheme的规范一直强行划定Scheme支撑尾递归优化。

  我们完成add函数以下

(define (add a b)
 (if (zero? a) b (add (- a 1) (+ b 1))))

  完成更加庞杂的奇偶推断

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

  运用Chez Scheme、Racket、guile测试,运用很大的数来运算,

  然后运用top来观察顺序的内存运用状况,我们发明,虽然CPU占用率多是100%,但内存的运用并不增添。就连guile如许的一个小的完成都是云云,从而它们都是相符规范而对尾递归举行优化的。

 

Common Lisp

 

  测完Scheme,再来测Scheme的本家兄弟,别的一种Lisp——Common Lisp

  先用Common Lisp完成add,由于Common Lisp将数据和历程用差别的定名空间,致使代码有点新鲜(好像很不数学)

(defun add(a b)
 (if (zerop a) b (funcall #'add (- a 1) (+ b 1))))

  运用clisp来运转

  (add 10000 10000)

  效果就

*** - Program stack overflow. RESET

  由于没有尾递归优化的划定,所以关于那种无穷轮回,Common Lisp只能挑选迭代才保证不崩栈,比方运用do。运用do从新完成add以下

(defun add(a b)
 (do
  ((x a (- x 1))
   (y b (+ y 1)))
  ((zerop x) 
y)))

  云云,终究不崩栈了。然则好像也改变了Lisp的滋味,do明显此处只能在设想编译器、诠释器的时刻就得零丁完成,虽然按理Lisp下这些都应该是宏,然则不管用宏怎样将函数式编程映照为显现的迭代,由于尾clisp递归优化不支撑,则没法和体系供应的do一样。

  sbcl是Common Lisp的别的一个完成,在这个完成中,我们运用第一个add函数的版本,没有发作崩栈。我们再来完成一下奇偶推断

(defun is-odd(x) 
 (if (zerop x) '() (funcall #'is-even (- x 1))))
(defun is-even(x)
 (if (zerop x)  t (funcall #'is-odd (- x 1))))

  盘算

 (is-even 1000000000)

  过了几秒,返回了效果t,证实了sbcl对尾递归做了优化。也终究给了我们一个更加靠谱的Common Lisp的完成。

 

AWK

 

  挑选一种脚本言语来测试这个题目,运用GNU awk来完成add

awk '
function add(a,b)
{
   if(a==0)
       return b
    return add(a-1, b+1)
}
{print add($1, $2)}'

  运转后,用top来观察内存占用

  

   

 

  输入

  100000000 1

  让其做加法

  

 

 

  内存运用霎时迸发,直到历程被体系KO。

  话说,awk没有对尾递归优化也属一般,而且关于内存的运用还真不控制,凌驾了我的设想。不过这也与言语的目标有关,awk本就没打算做这类事变。

 

Haskell

 

  直接上以下Haskell顺序来形貌奇偶推断

is_even x = if x==0 then True else is_odd (x-1)
is_odd x = if x==0 then False else is_even (x-1)
main = print (is_even 1000000000)

  用ghc编译运转,输出True,用时33秒。

  Haskell不亏是号称纯函数式编程,尾递归优化无条件支撑。

 

Prolog

 

  本不想测prolog,由于起首它并没有所谓的函数,靠的是谓词演变来盘算,推理上的优化是其基础需求。尾递归本不属于Prolog的支撑领域,固然能够组织相似尾递归的东西,而且Prolog固然能够完成,不会有牵挂。

  比方我们完成奇偶推断以下:

is_even(0, 1).
is_even(X, T) :- M is X-1, is_odd(M, T).
is_odd(0, 0).
is_odd(X, T) :- M is X-1, is_even(M, T).

  查询

  ?- is_even(100000000,S),write(S),!.

  获得

  1

 

Erlang

 

  先写一个model包括add/even/odd三个函数,

-module(mytest).
-export([add/2,even/1,odd/1]).
add(A,B)->if A==0->B;true->add(A-1,B+1) end.
even(X)->if X==0->true;true->odd(X-1) end.
odd(X)->if X==0->false;true->even(X-1) end.

  加载模板,并测试以下

1> c(mytest).
{ok,mytest}
2> mytest:add(1000000000,1000000000).
2000000000
3> mytest:even(1000000000).          
true
4> mytest:odd(1000000000).
false

  明显,Erlang对尾递归支撑很好。

 

golang

 

  编写add的完成以下

package main
import "fmt"
func add(a int, b int) int {
    if (a==0) {
        return b;
    }
    return add(a-1,b+1);
}

func main() {
    fmt.Println(add(100000000, 0))
}

  

  运转

  go run add.go

  立时崩溃

 

Lua

 

  Lua的作者和JS的作者一样是Lisp的粉丝,Lua的后期设想(从Lua4)听说参考了Scheme。

function odd(x)
    if (x==0) then
        return false
    end
    return even(x-1)
end
function even(x)
    if (x==0) then
        return true
    end
    return odd(x-1)
end
print(odd(io.read()))

 

  运转

  echo 1000000000 | lua5.3 x.lua

  历程当中,视察内存没有明显变化,以后打印出了false

  看来,最少参考了Scheme的尾递归优化。

 

Ruby

 

  Ruby的作者松本行弘也是Lisp的粉丝,固然,我想大多数编程言语的作者都会是Lisp的粉丝,由于它会给人许多启示。

  完成奇偶推断以下:

#!/usr/bin/ruby
 
def odd(x)
    if x == 0
        return 0
    end
    return even(x-1)
end

def even(x)
    if x == 0
        return 1
    end
    return odd(x-1)
end

puts even gets.to_i

 

  但是,数字大一点点,就崩栈了。Ruby并不支撑尾递归优化。

 

尾声

 

  测了这些言语以及响应的东西,实在照样在于函数式编程里,尾递归完成的迭代是我们常常运用的手腕,编译器/诠释器的支撑就会显得很重要了。再深一步,我们会去想一想,编译器/诠释器此处该怎样做,是不是能够对现有的设想举行修正呢?或许,对该言语/东西的将来怀着什么样的期待呢?再或许,假如我们本身也设想一种编程言语,会怎样设想这类编程言语呢?……

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
种种编程语言对尾递归的支撑

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282196.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>