标签: tail-recursion

关于尾递归函数有几个问题,例如这个和这个但是找不到类似于下面的东西.

我的理解是尾部调用优化函数应该在其最后一次调用中返回累积值而无需进一步评估.使用因子函数很容易理解,例如,它被优化为循环2.但在其他情况下,例如在下面,最后一次电话是什么,并不总是显而易见的？它们中有很多因为函数在体内不止一次被称为递归.

Brian提出了一种查找方法,但我不确定如何使尾调用优化.我可以将--tailcalls标志传递给编译器自动执行但是它总是成功吗？

f并g返回相同的类型.

type T = T of int * T list

let rec myfunc f (T (x,xs)) =
    if (List.isEmpty xs) then f x
    else 
        List.fold g acc (List.map (fun xxs -> myfunc f xxs) xs)

任何有关尾部调用优化上述代码的帮助都将非常感激.

这是一个Haskell函数,它接受一个数字n并返回第n个斐波纳契数.(我使用了索引方案,使得第0个数字为0,第1个数字为1,第2个数字为1,第3个数字为2,依此类推.)

fib :: (Integral a) => a -> a
fib 0 = 0
fib n = fibhelper n 0 1

fibhelper :: (Integral a) => a -> a -> a -> a
fibhelper 1 x y = y
fibhelper n x y = fibhelper (n-1) y (x+y)

现在,假设为了效率,我想绕过Haskell的懒惰评估并强制评估更新的参数(例如使用$!运算符？)最优雅/惯用的方法是什么？

结果总是得到"1".:(
这个功能有什么问题？

    def power(base: Int, exp: Int): BigInt = {
        def _power(result: BigInt, exp: Int): BigInt = exp match {
            case 0 => 1
            case _ => _power(result*base, exp-1)
        }
        _power(1, exp)
    }

我无法理解为什么以下函数会导致无限循环:

import Data.List

isTrue = foldl' (&&) False (repeat False)

我编写了一个程序来从表达式列表中递归地评估prolog中的修复后表达式.例如,给出以下列表:

[+,1,2]

它应该返回3.我构建谓词的方式是递归调用自身直到它到达列表的末尾,以便它向后读取值.(与从左到右阅读此列表相同:[2,1,+]).

我的问题是,当我尝试通过递归调用返回多个值时,所有值都会突然消失.

这是代码:

eval_list([Head|Tail],_,Result):-
   Tail==[], % last element of list
   Result=Head,
   write(Head),
   write(' was stored in Result!\n').

eval_list([Head|Tail],Store1,Result):-
      eval_list(Tail,Store2, NewResult),
      (\+integer(Store2))
   ->
      % if no integer is bound to Store2, bind Store1 to Head
      Store1=Head,
      Result is NewResult,
      write(Head),
      write(' is stored value!\n')
   ;  (integer(Store2)) ->
    % if an integer is bound to store2, we perform operation specified by the Head with the stored number
      X is Store2+NewResult,
      Result is X,
      write('performed operation!\n')
   ;
      % if doesnt catch …

#include <iostream> 

int foo(int i){ 
     return foo(i + 1);
} 

int main(int argc,char * argv[]){ 
     if(argc != 2){ 
         return 1; 
     } 
     std::cout << foo(std::atoi(argv[1])) << std::endl; 
} 

%clang ++ -O2 test.cc

%time./ a.out 42

1490723512

./a.out 42 0.00s用户0.00s系统69%cpu 0.004总计

%time./ a.out 42

1564058296

./a.out 42 0.00s用户0.00s系统56%cpu 0.006总计

%g ++ -O2 test.cc

%./ a.out 42 #infinte递归

^ C

% clang++ --version 
clang version 3.3 (tags/RELEASE_33/final) 
Target: x86_64-apple-darwin12.4.0 
Thread model: posix 
% g++ --version 
i686-apple-darwin11-llvm-g++-4.2 (GCC) 4.2.1 (Based on Apple Inc. build …

Clojure说我无法recur从非尾部位置打电话.

这不是尾巴的位置吗？

那么我的循环中的尾部位置是什么？

(loop [i 20]
    (for [x (range 1 21)]
      (if (zero? (rem i x))
        i
        (recur (+ i 1)))))

我必须以两种方式在Haskell中实现sum函数.一个函数具有尾递归,另一个函数没有尾递归.

这是没有尾递归的那个,它完美地工作

sum1 x = if x==0 then 0 else x + sum1(x-1)

这是我的尾递归尝试,它不起作用:

sum2 x = help 0 y
help x y = if y==0 then x else help(x+y,y-1)

有人可以指出错误吗？

我是F#的新手,想通过递归方式实现列表中最不常见的多重函数,例如lcm(a,b,c)= lcm(a,lcm(b,c)),其中lcm为两个元素是从gcd计算的.

我有以下代码.我尝试将lcm函数的输入与两个元素的列表进行匹配,否则将是一个通用列表,我将其拆分为第一个元素和剩余部分."lcm(tail)"部分给出了编译器错误.它说它应该有类型"int"但是类型为"int list - > int".它看起来像是说"lcm tail"本身就是一个函数,我不明白.为什么不是int？

let rec gcd a b =
    if b = 0
        then abs a
    else gcd b (a % b)

let lcmSimple a b = a*b/(gcd a b)

let rec lcm list = function
    | [a;b] -> lcmSimple a b
    | head::tail -> lcmSimple (head) (lcm (tail))

最好的祝福.

我想知道,当重写"常规"递归函数作为尾递归函数时,我该如何处理？有某种策略吗？

例如:我有这个简单的函数,我想把它变成一个尾递归的函数:

int rec(int n) {
    if (n % 2 || n > 10) {
    return n;
    }
    return  rec(n+1) + rec(n+2);
}

任何帮助表示赞赏.