标签: tail-recursion

假设我写这样的代码:

tailrec fun odd(n: Int): Boolean =
        if (n == 0) false
        else even(n - 1)

tailrec fun even(n: Int): Boolean =
        if (n == 0) true
        else odd(n - 1)

fun main(args:Array<String>) {
    // :( java.lang.StackOverflowError
    System.out.println(even(99999))
}

如何让Kotlin优化这些相互递归的函数,以便我可以在main不抛出StackOverflowError的情况下运行？该tailrec关键字适用于单函数递归,但没有更复杂的.我还看到一个警告,即在使用tailrec关键字的地方没有找到尾调用.也许这对编译器来说太难了？

看看这个Scala代码:

def rec(n: Int) {
  if (n > 1) {
    val d = n / 2
    rec(d)
//    if (d > 1)  // abort loop
      rec(n/d)
  }
}

此代码将导致无限循环.由于尾递归优化,我没有得到StackOverflowError.

用jad反编译我得到了这个Java代码:

public void rec(int n)
{
    int d;
    for(; n > 1; n /= d)
    {
        int i = n;
        d = i / 2;
        rec(d);
    }
}

在循环的最后一行,该方法调用自身,因此我不理解尾调用位置.谁可以解释这个？

这里似乎是我可以从我刚刚完成的如何设计程序(简化球拍)课程中获得的两件最重要的事情,直接来自课程的讲义:

1)尾部调用优化,以及非功能语言的缺乏:

可悲的是,大多数其他语言不支持TAIL CALL OPTIMIZATION.换句话说,即使是尾调用,它们也会构建堆栈.

尾调用优化是在70年代中期发明的,远在大多数语言的主要元素开发之后.因为它们没有尾调用优化,所以这些语言提供了一组固定的LOOPING CONSTRUCTS,可以遍历任意大小的数据.

a)在没有特色的过程语言中,这种类型的优化有哪些等价物？b)使用那些等价物是否意味着我们避免在类似情况下在没有它的语言中建立堆栈？

2)变异和多核处理器

这种机制几乎是你编程的任何其他语言的基础.我们推迟到目前为止推出它有几个原因:

• 尽管是基础,但它却非常复杂

• 过度使用它会导致程序无法并行化(在多个处理器上运行).由于多核计算机现​​在很常见,因此仅在需要时使用突变的能力变得越来越重要

• 过度使用变异也会使程序难以理解,难以很好地测试它们

但是可变变量很重要,学习这个机制将为您提供更多准备工作Java,Python和许多其他语言.即使在这些语言中,您也希望使用称为"主要是函数式编程"的样式.

在学习本课程之前,我学习了一些Java,Python和C++,因此认为变异是理所当然的.现在已经被上述声明全部抛到了空中.我的问题是:

a)我在哪里可以找到有关第二篇子弹中建议内容的更多详细信息,以及如何处理这些内容,以及b)"大多数功能性编程"风格会出现什​​么样的模式,而不是更粗心的风格我可能本来会继续使用其他语言而不是参加这门课程？

假设我有一个以递归方式访问的结构。

伪代码：

visit(node n)
{
    if (n == visited)
         return;

    //do something
    setVisited(n);
    foreach child_node in n.getChildren(){
        visit(child_node);
    }

}

根据这个线程尾递归可以在以下情况下发生：

尾递归基本上是在以下情况下：

• 只有一个递归调用
• 该调用是函数中的最后一条语句

在上面的伪代码中，递归调用是最后一条语句，但由于调用发生在循环内，因此存在多个递归调用。我猜编译器无法检测到尾递归。

我的问题是：

无论如何重构上面的代码以使其尾递归？我正在寻找一种不会删除递归的解决方案，如果有的话（例如，我不想使用堆栈来模拟递归并将其转换为迭代函数）。

这可能吗？

如果语言是相关的，我正在使用 C++。

我曾尝试在GCC 4.4.5在Linux在Mac OSX(4.2.1的Xcode)和下面的代码和gcc-LLVM 此.以下是相关功能的来源和生成的反汇编.(补充:编译gcc -O2 main.c)

#include <stdio.h>
__attribute__((noinline))
static void g(long num)
{
        long m, n;
        printf("%p %ld\n", &m, n);
        return g(num-1);
}
__attribute__((noinline))
static void h(long num)
{
        long m, n;
        printf("%ld %ld\n", m, n);
        return h(num-1);
}
__attribute__((noinline))
static void f(long * num)
{
        scanf("%ld", num);
        g(*num);
        h(*num);        
        return f(num);
}
int main(void)
{
        printf("int:%lu long:%lu unsigned:%lu\n", sizeof(int), sizeof(long), sizeof(unsigned));
        long num;
        f(&num);                 
        return 0;
}

08048430 <g>:
8048430:    55                   push   %ebp
8048431:    89 …

如何判断OCaml是否将特定函数识别为尾递归？特别是,我想知道OCaml编译器是否识别短路运算符和尾递归

感谢Jeffrey在下面的回答,我尝试了这个简单的功能

let rec check_all l =
    match l with
    | [] -> true
    | hd :: tl ->
        hd && check_all tl

事实上,它确实优化到:

camlTest__check_all_1008:
        .cfi_startproc
.L102:
        cmpl    $1, %eax
        je      .L100
        movl    (%eax), %ebx
        cmpl    $1, %ebx
        je      .L101
        movl    4(%eax), %eax
        jmp     .L102
        .align  16
.L101:
        movl    $1, %eax
        ret

ES6对尾调用优化的支持是否涵盖了生成器中的尾调用？

假设我有一个整数> = 0的生成器:

var nums = function* (n) {
    n = n || 0;
    yield n;
    yield* nums(n + 1);
};

目前,在Chrome和Firefox中,它会在每次递归调用时添加堆栈级别,并最终遇到"超出最大调用堆栈大小"错误.一旦ES6完全实现,这仍然会发生吗？

(我知道我可以迭代地编写上面的生成器而不会遇到错误.我只是想知道TCO是否会处理递归定义的生成器.)

我有一个递归函数,耗尽调用堆栈是我遇到的问题.我知道我可以使用带有setTimeout的流,promises,但我想编写触发尾调用优化的代码.到目前为止,只有Webkit似乎已经实现了尾调用优化(TCO).除了知道理论之外,有没有办法检查我的代码是否会触发TCO,无论是使用devtools还是检查Webkit编译器的输出？

我有一个计算任何数字的阶乘的程序.当我尝试将其作为100,000这样的大数字时,它会在它达到0之前停止.我猜这是一种防止出现问题的安全机制.

虽然这很好,但它可以防止程序计算大量数字.在我的程序中,变量x达到0后,它会停止递归函数.所以不需要这个"安全网".

这是我的代码供参考:

#include <iostream>
#include <string>

int answer = 1;
int recursive(int x);
using std::cout;
using std::cin;
int main() {

    recursive( 100000 );

}


int recursive( int x ) {
    cout << x << "\n";
    answer = x * answer;
    x--;
    if ( x > 0 ) {
        recursive( x );
    }
    else {
        cout << "Answer: " << answer << "\n";
    }
}

有没有办法解决这个障碍？

我尝试了解编程中的良好实践,并且我坚持这个问题.我知道在Java中,递归函数可能是"痛苦的屁股"(有时),我尝试尽可能多地实现该函数的尾部版本.是值得打扰这个还是我应该用老式的方式做什么？这两个函数之间有什么区别(在Kotlin中):

tailrec fun tail_fibonacci(n : BigInteger, fib1 : BigInteger = BigInteger.ZERO , fib2 : BigInteger = BigInteger.ONE) :
BigInteger {
    return when(n){
        BigInteger.ZERO -> fib1
        else -> tail_fibonacci(n.minus(BigInteger.ONE),fib1.plus(fib2),fib1)
    }
}

fun iterative_fibonacci(n: BigInteger) : BigInteger {
    var count : BigInteger = BigInteger.ONE
    var a : BigInteger = BigInteger.ZERO
    var b : BigInteger = BigInteger.ONE
    var c : BigInteger
    while(count < n){
        count += BigInteger.ONE
        c = a + b
        a = b
        b = c
    }
    return b
}