相关疑难解决方法(0)

一个reddit线程提出了一个显然有趣的问题:

尾递归函数可以简单地转换为迭代函数.其他的,可以通过使用显式堆栈进行转换.可每次递归转化为迭代？

帖子中的(计数器？)示例是对:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

在我看来,在C和C++中进行尾递归优化是完美的,但是在调试时我似乎永远不会看到表示此优化的帧堆栈.这有点好,因为堆栈告诉我递归的深度.但是,优化也会很好.

是否有任何C++编译器进行此优化？为什么？为什么不？

我如何告诉编译器这样做？

• 对于MSVC:/O2或/Ox
• 对于海湾合作委员会:-O2或-O3

如何在某种情况下检查编译器是否已完成此操作？

• 对于MSVC,启用PDB输出以跟踪代码,然后检查代码
• 对于GCC ..？

我仍然会建议如何确定编译器是否对某个函数进行了优化(尽管我发现它让人放心,Konrad告诉我假设它)

总是可以通过进行无限递归来检查编译器是否完成此操作,并检查它是否导致无限循环或堆栈溢出(我用GCC做了这个并且发现这-O2已经足够了),但我想成为能够检查我知道的某个功能无论如何都会终止.我很想有一个简单的方法来检查这个:)

经过一些测试,我发现析构函数破坏了进行优化的可能性.有时可能值得更改某些变量和临时值的范围,以确保它们在return语句开始之前超出范围.

如果在尾调用后需要运行任何析构函数,则无法进行尾调用优化.

如何判断gcc(更具体地说,g ++)是否在特定函数中优化尾递归？(因为它出现了几次:我不想测试gcc是否可以优化尾递归.我想知道它是否优化了我的尾递归函数.)

如果您的答案是"查看生成的汇编程序",我想知道我正在寻找什么,以及我是否可以编写一个简单的程序来检查汇编程序以查看是否存在优化.

PS.我知道这似乎是问题的一部分,如果有的话,C++编译器会进行尾递归优化吗？从5个月前.但是,我不认为这个问题的这一部分得到了令人满意的答复.(答案是"检查编译器是否进行了优化(我知道)的最简单方法是执行调用,否则会导致堆栈溢出 - 或者查看汇编输出.")

我想检查g ++是否支持尾调用,所以我编写了这个简单的程序来检查它:http://ideone.com/hnXHv

using namespace std;

size_t st;

void PrintStackTop(const std::string &type)
{
    int stack_top;
    if(st == 0) st = (size_t) &stack_top;
    cout << "In " << type << " call version, the stack top is: " << (st - (size_t) &stack_top) << endl;
}

int TailCallFactorial(int n, int a = 1)
{
    PrintStackTop("tail");
    if(n < 2)
        return a;
    return TailCallFactorial(n - 1, n * a);
}

int NormalCallFactorial(int n)
{
    PrintStackTop("normal");
    if(n < 2)
        return 1;
    return …

我有这个函数,我写的是非常慢,因为PHP不能很好地处理递归.我试图将它转换为while循环,但我无法绕过如何做到这一点.

谁能给我一些提示？

    public function findRoute($curLoc, $distanceSoFar, $expectedValue) {

    $this->locationsVisited[$curLoc] = true;
    $expectedValue += $this->locationsArray[$curLoc]*$distanceSoFar;

    $at_end = true;
    for($i = 1; $i < $this->numLocations; $i++) {
        if($this->locationsVisited[$i] == false) {
            $at_end = false;

            if($expectedValue < $this->bestEV)
                $this->findRoute($i, $distanceSoFar + $this->distanceArray[$curLoc][$i], $expectedValue);
        }
    }

    $this->locationsVisited[$curLoc] = false;

    if($at_end) {
        if($expectedValue < $this->bestEV) {
            $this->bestEV = $expectedValue;
        }
    }
}