`
argan
  • 浏览: 129554 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

并不是所有的时候都应该选择尾递归

阅读更多

要实现一个函数,参数是一个list,结果是将list里每个数字都+1,返回一个新的list,会怎么实现呢?

 

看代码,哪个函数性能最好?(除了add2,因为他的结果是不正确的)

-module(t).

-compile(export_all).

add1([]) -> [];
add1([H|T]) -> [H+1|add1(T)].

add2(R) -> add(R,[]).

add3(R) -> lists:reverse(add(R,[])).

add4([]) -> [];
add4(L) -> lists:map(fun(X) -> X+1 end,L).

add([],R) -> R;
add([H|T],R) -> add(T,[H+1|R]).

t(N) ->
   L = lists:seq(1,N),
   {T1,_}=timer:tc(a,add1,[L]),
   {T2,_}=timer:tc(a,add2,[L]),
   {T3,_}=timer:tc(a,add3,[L]),
   {T4,_}=timer:tc(a,add4,[L]),
   io:format("~p ~p ~p ~p ~n",[T1,T2,T3,T4]).

 函数说明:

*add1 是最简单的实现,没有使用尾递归

*add2 使用尾递归,最后没有reverse,结果是不正确的,仅仅用来比较

*add3 使用尾递归

*add4 使用list comprehension

 

在我的笔记本上运行,在N比较小(N<100000)的情况下,add3几乎总是比add1快,但是N比较大(N>100000)的时候,add1经常比add3快,说明lists:reverse的消耗还是挺大的

 

这个场景说明了几个问题:

*在list比较大的时候,reverse操作消耗还是很大的(废话)

*erlang的编译器会对类似add1的情况做优化,如果没有优化的话,应该会死的很惨

*当使用尾递归会带来额外的事情的时候,需要权衡一下,是否应该选用

*如果能事先知道程序运行的场景(这里是N的大小),写出来的程序性能才能更好

 

似乎都是废话,仅当记录。

分享到:
评论
3 楼 mryufeng 2009-07-09  
Wrangler 会专门对这个进行重构 那说明Add3是最佳实践。
2 楼 cryolite 2009-07-09  
add1要省内存,尾递归的那个耗内存比较大
1 楼 argan 2009-07-08  
果然:
It is one of the principal Myths of Erlang Performance† that tail recursion is much more efficient than direct recursion in Erlang. Perhaps this was true in the early days of the language, but  optimizations applied between releases 7 and 12 have meant that it’s no longer true that tail recursion will give you a more efficient program.

The advice of the developers of the system is “The choice is now mostly
a matter of taste. If you really do need the utmost speed, you must
measure. You can no longer be absolutely sure that a tail-recursive func
tion will be the fastest in all circumstances.”

相关推荐

    详解python使用递归、尾递归、循环三种方式实现斐波那契数列

    但Python标准解释器并未对尾递归进行优化,所以尾递归在Python中的效果并不明显。 3. **循环**: 循环是最有效的方法,如 `Fib_circle` 函数所示。通过循环,我们可以避免递归带来的额外开销,只需线性时间复杂度...

    C#中的尾递归与Continuation详解

    TailRecursively(n - 1, acc2, acc...尽管C#标准库并不直接支持尾递归优化,但开发者可以通过模拟Continuation或使用异步编程来实现类似的优化效果。理解并熟练运用这些技术,可以帮助我们编写更加高效、可维护的代码。

    关于尾递归的使用详解

    并非所有语言都支持尾递归优化,即使支持的语言也可能只在编译时进行优化。因此,在优化代码时,需要先了解目标语言对尾递归的支持情况。 **总结** 尾递归是一种高效的递归形式,尤其在处理深度递归和大量数据时,...

    C.rar_instead5ss_尾递归_整数转为二进制数

    需要注意的是,大多数C编译器并不默认优化尾递归,除非开启特定的编译选项(如GCC的`-O2`或`-ftailcall-opt`)。在实际编程中,虽然尾递归可以优化内存使用,但在某些情况下,可能需要结合循环等其他结构来实现更...

    尾递归详细总结分析

    然而,不是所有递归都可以转化为尾递归。当递归调用不是函数的最后一行,或者递归调用的结果需要与函数内部的其他计算结合时,就不能进行尾递归优化。 总的来说,理解并掌握尾递归的概念对于编写高效、可维护的递归...

    关于尾递归和Cooper变换

    通过以上分析可以看出,尾递归与 Cooper 变换都是计算机科学领域内非常重要的概念和技术。尾递归可以帮助优化递归算法,提高程序效率;而 Cooper 变换则提供了一种方法,可以将非尾递归的递归函数转换为尾递归的形式...

    JS尾递归的实现方法及代码优化技巧

    在某些语言中,如Scala,编译器会自动处理尾递归优化,但在JavaScript中,虽然V8引擎在某些情况下支持尾递归优化,但并不是所有浏览器或环境都提供这种优化。 在JavaScript中,如果解释器不支持尾递归优化,我们...

    Python递归及尾递归优化操作实例分析

    汉诺塔是一个经典的递归问题,目标是将所有盘子从柱子A移动到柱子C,但每次只能移动一个盘子,且任何时候大盘子都不能位于小盘子之上。递归解决方案可以分为三步: 1. 把n-1个盘子从A移动到B。 2. 把最大的盘子从A...

    Python中使用装饰器来优化尾递归的示例

    然而,Python解释器本身并不支持尾递归优化,因此我们需要采取额外措施来实现这一点。 #### 使用装饰器优化尾递归 接下来,我们将通过一个具体的例子——斐波那契数列——来展示如何利用装饰器来优化尾递归。 ###...

    递归函数示意图.pdf

    在尾递归优化的部分,引入了一个辅助函数f_helper(x, result),其目的是使递归过程在函数的尾部发生,这样可以提高效率,因为很多现代的编程语言,如Python,不支持真正的尾递归优化,所以对于深层递归,可能会导致...

    .net 递归算法 .net 递归算法.net 递归算法

    因此,非尾递归或深度较大的递归可能需要优化,如使用迭代代替或者尾递归优化。 - **终止条件**:确保每个递归调用都向基础情况靠近,否则可能会导致无限递归。 - **理解问题与分解**:正确理解和分解问题是成功...

    es6函数之尾递归用法实例分析

    而尾递归则通过在递归调用后不执行任何其他操作,避免了这一问题,从而优化了内存使用。 首先,让我们理解什么是尾递归。在函数中,如果递归调用是最后一个执行的操作,并且没有其他计算跟随,那么这个递归调用就是...

    C#函数式编程中的递归调用之尾递归详解

    然而,C#的编译器并不默认进行尾递归优化,而是等到JIT(Just-In-Time)编译器在运行时才会进行这种优化,而且仅限于64位环境。 让我们深入理解尾递归的工作原理。假设我们有一个计算阶乘的函数,通常的递归实现...

    浅析递归

    1. **尾递归**:如果递归调用是函数的最后一个操作且没有其他操作依赖于递归调用的结果,那么可以优化为尾递归,一些编译器和解释器会优化尾递归,避免栈溢出。 2. **记忆化**:对已经计算过的子问题结果进行缓存,...

    java递归

    遗憾的是,标准的Java并不支持尾递归优化。 6. **调试递归**:由于递归涉及多个函数调用,调试递归函数可能会比较复杂。使用调试器的步进功能可以帮助理解每个递归层级的执行过程。 举例来说,计算阶乘可以使用...

    java 递归问题文档

    6. **尾递归优化**:某些Java编译器支持尾递归优化,这允许在不增加额外堆栈空间的情况下进行递归调用。不过,Java标准版目前并不默认开启这一优化,但在Java 14及以上版本的JDK中,可以使用`@jdk.internal.vm....

    迭代与递归的区别

    因此,在使用递归时,有时候需要考虑使用尾递归优化或转换为迭代形式来避免栈溢出。 总之,迭代与递归各有适用场景。迭代适用于问题规模较小,或者已知需要重复执行的次数的情况。而递归适用于问题能够自然地分解为...

Global site tag (gtag.js) - Google Analytics