标签: tail-recursion

我正在进行以下Erlang练习:

编写一个函数,给定一个列表列表,将它们连接起来.例:

concatenate([[1,2,3], [], [4,five]]) ? [1,2,3,4,five].

我想出了这个:

concatenate([]) ->
    [];
concatenate([[H]|Tail]) ->
    [H|concatenate(Tail)];
concatenate([[]|Tail]) ->
    concatenate(Tail);
concatenate([[H|T]|Tail]) ->
    [H|concatenate([T|Tail])].

哪个有效,但我注意到我正在做这[T|Tail]件事.

第一个问题

这仍然被认为是直接递归吗？

在那之后,我摆脱了它[T|Tail]并使用了累加器(如下所示).

第二个问题

现在第二个代码是否考虑了尾递归？

这本书提示使用辅助函数(第二个代码正在做),但它看起来相当冗长.是因为我错过了什么吗？

concatenate([]) ->
    [];
concatenate([[H]|Tail]) ->
    [H|concatenate(Tail)];
concatenate([[]|Tail]) ->
    concatenate(Tail);
concatenate([[H|T]|Tail]) ->
    [H|concatenate(T,Tail)].

concatenate([],Tail) ->
    concatenate(Tail);
concatenate([H],Tail) ->
    [H|concatenate(Tail)];
concatenate([H|T],Tail) ->
    [H|concatenate(T,Tail)].

在我开始之前:是的,这是大学的家庭作业.在我被告知我是懒惰和邪恶之前:这部分功课是转换我们已经拥有的两个功能,这个是第6个.

(define (flatten-list a-list)
  (cond ((null? a-list) '())
      ((list? (car a-list)) 
       (append (flatten-list (car a-list)) (flatten-list (cdr a-list))))
      (else (cons (car a-list) (flatten-list (cdr a-list))))))

正如您所猜测的,该函数即使嵌套也会使列表变平.转换的具体问题出现在(list？(car a-list))条件中,我正在进行两次递归调用.我已经做了斐波纳契,我可以通过在尾递归上只有两个"累加器"来做.但是,我还没有接受过这方面的培训,也不知道应该怎么做.

如果我得到提示而不是结果,我将不胜感激.谢谢!

假设我有一个像这样的简单函数:

int all_true(int* bools, int len) {
    if (len < 1) return TRUE;
    return *bools && all_true(bools+1, len-1);
}

这个函数可以用更明显的尾递归样式重写,如下所示:

int all_true(int* bools, int len) {
    if (len < 1) return TRUE;
    if (!*bools) return FALSE;
    return all_true(bools+1, len-1);
}

从逻辑上讲,两者之间没有差别; 假设bools只包含TRUE或FALSE(明智地定义),它们完全相同.

我的问题是:如果编译器足够智能以优化第二个作为尾递归调用,那么假设它以相同的方式优化第一个是合理的,假设"&&"短路？显然,如果使用非短路运算符,这将不是尾递归的,因为两个表达式都会在运算符被应用之前进行求值,但我对短路情况感到好奇.

(在我收到大量评论告诉我C编译器通常不优化尾递归调用之前:考虑这是一个关于使用短路运算符优化尾递归调用的一般性问题,不依赖于语言.我将是很高兴在Scheme,Haskell,OCaml,F#,Python中重写这个,或者如果你不理解C,那么你还有什么其他的东西.)

我试图在Data.Map.Map上实现Functor fmap,但是我收到了一个错误.我确信我不需要将Map转换为List以及从列表转换为了使其工作,但这是迄今为止我提出的最好的.

class Functor' f where
    fmap' :: (a -> b) -> f a -> f b

instance Functor' (Map.Map k) where
    fmap' f m
        | Map.null m = Map.empty
        | otherwise = let x:xs = Map.toList m
                          mtail = Map.fromList xs
                          a = fst x
                          b = snd x
                      in  Map.insert a (f b) (fmap f mtail)

错误:

No instance for (Ord k)
  arising from a use of `Map.fromList'
In the expression: Map.fromList xs
In an equation for `mtail': …

我知道在这个SO答案中写出的尾递归算法是什么.然而,我正在通过麻省理工学院的快速排序算法视频,并在18:30秒教授说这是尾递归算法.我无法连接这是如何尾递归.我们不是在递归的任何步骤进行计算,还是我们？你能解释为什么这被引用作尾递归算法的一个例子.请以我知道递归算法是什么为前提,给出答案.我不清楚的部分是为什么它被称为尾递归？

我在Elixir中写了一个简单的例子,虽然它有效但我真的不明白怎么做.

defmodule MyList do
  def sum([],acc \\ 0), do: acc
  def sum([head | tail], acc), do: sum(tail,acc + head)
end

当我调用MyList.sum时,我得到了预期的结果

sum([]) => 0
sum([1,2,3]) => 6

我无法在第二个和中添加默认参数,因为编译器会抛出错误

def sum/2 has default values and multiple clauses, use a separate clause for declaring defaults

所以我的问题是,sum([1,2,3])如何运作？它与任何定义都不匹配.该函数仍然是尾递归的吗？

例如,如何合并两个已排序整数的Streams？我认为这是非常基本的,但只是发现它根本不重要.下面的一个不是尾递归的,当Streams很大时它会堆栈溢出.

def merge(as: Stream[Int], bs: Stream[Int]): Stream[Int] = {
  (as, bs) match {
    case (Stream.Empty, bss) => bss
    case (ass, Stream.Empty) => ass
    case (a #:: ass, b #:: bss) =>
      if (a < b) a #:: merge(ass, bs)
      else b #:: merge(as, bss)
  }
}

我们可能希望通过引入累加器将其转换为尾递归.但是,如果我们预先挂起累加器,我们只会得到一个逆序流; 如果我们用累加(#:: :)附加累加器,它就不再是懒惰(严格)了.

这可能是什么解决方案？谢谢

在函数式编程中有这种CPS技巧,它采用非尾递归函数并在连续传递样式(CPS)中重写它,从而使其尾递归.很多问题实际上涵盖了这一点,比如

• https://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/
• F#:哪个内存区域是存储的延续:堆栈还是堆？
• 为什么延续避免stackoverflow？

举一些例子

let rec count n = 
    if n = 0
      then 0
      else 1 + count (n - 1)

let rec countCPS n cont =
    if n = 0
      then cont 0
      else countCPS (n - 1) (fun ret -> cont (ret + 1))

第一个版本count将在每次递归调用中累积堆栈帧,n = 60000在我的计算机上产生堆栈溢出.

CPS技巧的想法是countCPS实现是尾递归的,因此计算

let f = countCPS 60000

实际上将被优化为循环运行并且没有问题地工作.而不是堆栈帧,继续运行将在每一步中累积,但这是堆上的诚实对象,其中内存不会导致问题.因此CPS风格据说可以用于堆空间的堆栈空间.但我怀疑它甚至做到了这一点.

原因如下:通过实际运行延续来评估计算,从而countCPS 60000 (fun x -> x)打击我的堆栈!每次通话

countCPS (n - 1) (fun ret -> …

我使用以下示例来测试使用Babel和es2016预设的尾调用递归:

'use strict';

try {
    function r(n) {
        if (n%5000===0)
            console.log(`reached a depth of ${n}`);
        r(n+1);
    }
    r(0);
} catch (e) {
    if (!(e instanceof RangeError))
        throw e;
    else
        console.log('stack blown');
}

我的package.json档案是:

{
    "name": "tail-call-optimization",
    "version": "1.0.0",
    "description": "",
    "main": "index.js",
    "scripts": {
        "build": "babel es6 --out-dir es5 --source-maps",
        "watch": "babel es6 --out-dir es5 --source-maps --watch",
        "start": "node es5/app.js"
    },
    "author": "",
    "license": "ISC",
    "devDependencies": {
        "babel-cli": "^6.6.5",
        "babel-core": "^6.7.4",
        "babel-loader": "^6.2.4",
        "babel-polyfill": "^6.7.4",
        "babel-preset-es2016": …

我有这两个gcd函数的实现:

def gcd1(a,b)
  if a==b
    a
  elsif a>b
    if (a%b)==0
      b
    else
      gcd1(a%b,b)
    end
  else
    if (b%a)==0
      a
    else
      gcd1(a,b%a)
    end
  end
end
def gcd2(a,b)
  if(a==b)
    return a
  elsif b>a
    min,max=a,b
  else
    min,max=b,a
  end
  while (max%min)!=0
    min,max=max%min,min
  end
  min
end

函数gcd1是尾递归的,而gcd2使用while循环.

我已经验证了rubinius通过对因子函数进行基准测试来进行TCO,只有基数函数,基准测试显示递归版本和迭代版本是"相同的"(我使用的是基准测试版).

但是对于上述情况,基准测试显示gcd1比gcd2快至少两倍(递归速度是迭代速度的两倍,甚至更快).

我用来进行基准测试的代码如下:

Benchmark.ips do |x|
  x.report "gcd1 tail recursive" do
    gcd1(12016,18016)
  end
  x.report "gcd2 while loop" do
    gcd2(12016,18016)
  end
  x.compare!
end

结果 :

Warming up --------------------------------------
 gcd1 tail recursive    47.720k i/100ms
     gcd2 while loop    23.118k i/100ms
Calculating ------------------------------------- …