标签: tail-recursion

在Haskell,如果我写

 fac n = facRec n 1
   where facRec 0 acc = acc
         facRec n acc = facRec (n-1) (acc*n)

并使用GHC进行编译,结果会与我使用的结果不同

 fac 0 = 1
 fac n = n * fac (n-1)

我可以轻松地完成fac n = product [1..n]并避免整个事情,但我对如何尝试使用懒惰语言进行尾递归感兴趣.我知道我仍然可以获得堆栈溢出,因为thunks正在构建,但是当我使用累加器时,实际发生的事情实际上是不同的(就最终的编译程序而言)而不是我刚才说出的天真递归？除了提高可读性之外,遗漏尾递归是否有任何好处？如果我runhaskell用来运行计算而不是先编译它,答案是否会发生变化？

我编码了3个因子算法:

1. 首先,我希望Stack Overflow失败.没问题.
2. 其次,我尝试尾部重用调用,将先前的算法从递归转换为迭代.它不起作用,但我不明白为什么.
3. 第三,我使用trampoline()方法,并按照我的预期正常工作.

def factorial

factorial = { BigInteger n ->
    if (n == 1) return 1
    n * factorial(n - 1)
}
factorial(1000)  // Stack Overflow

factorial = { Integer n, BigInteger acc = 1 ->
    if (n == 1) return acc
    factorial(n - 1, n * acc)
}
factorial(1000)  // Stack Overflow, why???

factorial = { Integer n, BigInteger acc = 1 ->
     if (n == 1) return acc
     factorial.trampoline(n …

我在课堂上被告知,由于在递归调用之后计算了布尔运算符,因此以下函数不是尾递归的:

let rec exists p = function
    [] -> false
  | a::l -> p a || exists p l

但是这并没有将堆栈放在1000万大小的列表中,更重要的是,它是标准库中的实现.如果它不是尾递归,则没有理由使用这种形式而不是看似等效且明确的尾递归

let rec exists p = function
    [] -> false
  | a::l -> if p a then true else exists p l

所以看起来OCaml编译器能够在这样的简单情况下优化布尔运算,以利用尾递归.但是我注意到如果我像这样切换操作数的顺序

let rec exists p = function
    [] -> false
  | a::l -> exists p l || p a

然后堆栈确实在10米元素上爆炸.因此,当递归调用出现在右侧时,OCaml似乎只能利用这一点,这让我怀疑所有编译器都会用等效if表达式替换boolean op .有人可以确认或反驳这个吗？

谢谢你的时间.

我正在学习斐波那契函数,其中一个答案如下:

function fibonacci(n) {
    return (function(a, b, i) {
        return (i < n) ? arguments.callee(b, a + b, i + 1) : a;
    })(1, 1, 1);
}
console.log(fibonacci(51))

由于在ES5之后严格模式中禁止arguments.callee,所以我用函数名替换它.之后,我看到了i + 1部分,我用i ++替换它,结果是太多的递归.

function x(n){
    return (function y(a, b, i){
        return (i < n) ? y(b, a + b, i++) : a;
    })(1,1,1)
}
console.log(x(51))

经过几次调试后,我发现i + 1工作正常,而i ++没有.

那么,我使用i ++是错误的地方还是我根本不了解i ++？

Thnx再次.

我知道Python不支持尾调用优化.这是否意味着具有迭代过程的递归过程(如下面定义的阶乘)将消耗O(n)内存,或者没有延迟操作的事实意味着空间将是O(1)？

def factorial(n, accum=1):
    if n == 0:
        return accum
    else:
        return factorial(n-1, accum * n)

我尝试Expression在.NET 4.0中构建一个尾递归.

我可以构建它但是,这个编译的方法不是尾部调用优化的,尽管指定tailCall = true,生成的IL没有tail.前缀指令.

请告诉我如何构建尾调用优化递归Expression？

构建表达式如下.

using System;
using System.Linq.Expressions;

namespace ConsoleApplication2
{
    public delegate int RecursiveFunc(RecursiveFunc function, int acc, int n);

    internal class Program
    {
        private static void Main()
        {
            var funcParam = Expression.Parameter(typeof (RecursiveFunc));
            var accParam = Expression.Parameter(typeof (int));
            var nParam = Expression.Parameter(typeof (int));
            var constZero = Expression.Constant(0, typeof (int));

            var accumExpr = Expression.Add(accParam, nParam);
            var decrimentExpr = Expression.Decrement(nParam);

            var invokeExpr = Expression.Invoke(funcParam, funcParam, 
                accumExpr, decrimentExpr);

            var testExpr = …

我正在阅读" 真实世界的函数式编程 "一书,在阅读本书的例子之前,我试图提出自己的尾递归示例(见10.2,第265页).这本书的例子有效; 我的堆栈溢出.

我发现如果我使用元组参数或预先计算a + accum然后我的工作.我想了解原因.

let rnd = new System.Random()
let test2 = List.init 1000000 (fun _ -> rnd.Next(-50, 51))

let rec sum2 list accum =
  match list with
  | [] -> accum
  | a::b -> sum2 b a + accum

let result = sum2 test2 0

printfn "%d" result

我最近开始阅读SICP，并且对将递归过程转换为尾递归形式非常感兴趣。

对于“一维”情况（线性情况），例如斐波那契数列或阶乘计算，进行转换并不难。

例如，正如书中所述，我们可以按以下方式重写斐波纳契计算

(define (fib n)
    (fib-iter 1 0 n))
(define (fib-iter a b count)
    (if (= count 0) 
        b 
        (fib-iter (+ a b) a (- count 1))))

而且这种形式显然是尾递归的

但是，对于“二维”情况，例如计算Pascal三角形（SICP中的Ex 1.12），我们仍然可以轻松编写如下的递归解

(define (pascal x y) 
  (cond ((or (<= x 0) (<= y 0) (< x y )) 0)
        ((or (= 1 y) (= x y) ) 1)
        (else (+ (pascal (- x 1) y) (pascal (- x 1) (- y 1))))))

问题是，如何将其转换为尾递归形式？

我有一个问题来比较两棵树.如下所示:

case class Node(elem:String, child:List[Node])

为了比较树的每个元素,我有以下功能:

def compare(n1:Node, n2:Node): Boolean {
   if(n1.elem == n2.elem){
      return compare(n1.child, n2.child)
   }
}

def compare(c1:List[Node], c2:List[Node]): Boolean {
    while (c1.notEmpty) {
       //filter, map etc call function above to compare the element recursively
    }
}

基本上算法是针对n1中的每个元素,我们正在检查n2中的匹配.我被告知这是非常必要的方式而不是功能方式.什么是实现这种行为的功能性方法.换句话说,在比较孩子列表时,我们如何删除while循环？

最近我通过函数式编程风格实现了insert_sort算法,它变得更加简洁和声明.问题是如何将其更改为尾递归,如果列表的大小增加到10000,代码将抛出异常.

def InsertSort(xs: List[Int]): List[Int] = xs match {
    case Nil => Nil
    case x::rest => 
       def insert (x: Int, sorted_xs:List[Int]) :List[Int] = sorted_xs match{
           case Nil => List(x)
           case y::ys => if  (x <= y) x::y::ys else y::insert(x,ys)
       }
       insert(x,InsertSort(rest))
 }