scheme递归的优势在哪
发布网友
发布时间：2022-04-19 01:08
共2个回答
热心网友
时间：2022-04-19 02:37
尾递归的优势，是可以迭代，程序消耗的内存基本是恒定的
据我所知，尾递归不是大部分语言拥有的特性，C语言和lisp都用，连C++都没有，遑论其他语言了
chezscheme有很多优化选项，没开的话哪有优势？
尾递归，就是scheme相比python的一个绝对优势
热心网友
时间：2022-04-19 03:55
非尾递归形式:
scheme代码:
(define (fib n)
(if (or (= n 2)(= n 1))
1
(+ (fib (- n 1)) (fib (- n 2)))))
Python代码:
def fib(n):
if n==1 or n==2:
return 1
else:
return fib(n-1)+fib(n-2)
取n=40,实测结果:
scheme要等大概30秒才返回结果.( chez 和racket两个平台都差不多,chez略快)
Python慢些,要1分钟的样子.
n=100是不要想了.scheme和Python半天都算不出.我直接强制中断,没有测试.
我非常失望啊!!!
我的疑问是:
1.虽然比Python快,但是scheme仍然慢啊,看不出什么实质优势.
因为我之前看一些文章说递归和scheme联系非常密切,既然如此,在这一块上,scheme要有拿得出手的优势啊..为什么这么简单的一个n=100就让它吃不消了?这个测试的消耗时间上,它和Python有什么本质区别?退50步和退100步吗?
2.对于斐波拉契这种,scheme一定要转换成尾递归才算得快吗?
scheme:
(define (fib n fir sec)
(if (< n 3)
sec
(fib (- n 1) sec (+ fir sec))))
Python:
def fib(n,a=1,b=1):
if n>2:
return fib(n-1,b,a+b)
return b
如果是这样,那么它和Python有啥区别呢?比如对于n=900,大家都算得快了啊..都是1秒内返回结果....
我只发现了一个scheme的优势
(1)python无法处理n>996的情况(奇怪的是,996的时候Python仍然是算得非常快的,实在不知道为什么997就一下子罢工了)
(2)schme没有这种*,n=100000都只需要10几秒就完成了.
