标签: tail-call-optimization

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

我的理解是尾部调用优化函数应该在其最后一次调用中返回累积值而无需进一步评估.使用因子函数很容易理解,例如,它被优化为循环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)

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

在我看来,应该可以使用递归和尾调用优化在恒定空间和线性时间内向后打印循环链表.但是,由于在进行递归调用后尝试打印当前元素,我遇到了困难.通过检查反汇编,我看到函数被调用而不是跳转到.如果我将其更改为向前打印而不是向后打印,则可以正确消除函数调用.

我已经看到了这个相关的问题,但我特别感兴趣的是使用递归和TCO来解决它.

我正在使用的代码:

#include <stdio.h>

struct node {
    int data;
    struct node *next;
};


void bar(struct node *elem, struct node *sentinel)
{
    if (elem->next == sentinel) {
        printf("%d\n", elem->data);
        return;
    }
    bar(elem->next, sentinel), printf("%d\n", elem->data);
}

int main(void)
{
    struct node e1, e2;
    e1.data = 1;
    e2.data = 2;
    e1.next = &e2;
    e2.next = &e1;
    bar(&e1, &e1);
    return 0;
}

和编译

    $ g++ -g -O3 -Wa,-alh test.cpp -o test.o

更新:使用Joni的答案解决,略微修改循环列表

void bar(struct node *curr, struct node *prev, struct …

我有一个关于尾调用优化的问题，我需要知道这个 java 代码的行为方式：

private void doSomething(int v) {

    inf f = someCalculation(v);

    if (f < 0) doSomething(v/2);
    else doSomething(v*2);

}

这段代码是一个无意义的例子，但我的问题是，在这种情况下：

1. 第一个 doSomething() 调用会被优化吗？
2. 第二个 doSomething() 调用会被优化吗？
3. if/else 块以任何方式影响优化？

谢谢

编辑：

请提供一个示例，说明如果语言不是 Java 而是其他具有 TCO 的语言，您将如何执行此操作

据我所知，进行尾调用优化的一个前提是递归点应该是函数中的最后一句，并且递归调用的结果应该立即返回。但为什么？

以下是 TCO 的有效示例：

int factorial(int num) {
  if (num == 1 || num == 0)
    return 1;
  return num * factorial(num - 1);
}

那么，有了这个规则，下面的代码是不是也可以优化呢？为什么不？

#include <stdio.h>
int factorial(int num) {
  if (num == 1 || num == 0)
    return 1;
  int temp = num * factorial(num - 1);
  printf("%d", temp);
  return temp;
}

我想知道我应该如何向其他人解释为什么上述规则对于拥有 TCO 是必要的。但不仅仅是简单地跟随。

我试图理解为什么第一个main在无效时终止c,而第二个终止.从描述来看,这 main只是一个未经评估的thunk,executing它只是构建数据结构.我试图在这里应用相同的原理,看看为什么第一个主要没有终止.如果有人可以帮助我理解这一部分,或者给我指点理解这将是伟大的.除此之外,为什么GHCI无法将其识别为TCO？不符合定义吗？

main = loop                                                                     
  where                                                                         
   loop =  do                                                                   
     c <- getChar                                                               
     case valid c of                                                            
       Nothing -> return ()                                                     
       Just b  -> print b                                                       
     print c                                                                    
     loop                                                                       

> main :: IO ()
> main = loop
>   where
>   loop =  do
>     c <- getChar
>     case validate c of
>       Nothing -> return ()
>       Just b  -> do
>         print b
>         loop

谢谢.

我正在阅读On Lisp中的第2.8节(Tail Recursion).它有一个尾递归函数的例子:

(defun our-length-tr (lst)
  "tail recursive version with accumulator"
  (labels ((rec (lst acc)
             (if (null lst)
                 acc        
                 (rec (cdr lst) (1+ acc)))))
    (rec lst 0)))

它说许多 Common Lisp编译器会执行TCO,但您可能需要(proclaim '(optimize speed))在文件的顶部.

我怎么能确定我的编译器支持TCO,并且它会将我的函数编译为循环版本而不是递归版本？

我正在尝试编写一个 100% 迭代的程序，也就是说，函数永远不需要返回，因为在这样的返回之后不会发生任何事情。

换句话说，程序100%处于尾部位置。考虑以下玩具程序：

  def foo(): Unit =
    bar()

  def bar(): Unit =
    foo()

  try
    foo()
  catch
    case s: StackOverflowError =>
      println(" Stack overflow!")

调用 foo 确实会导致堆栈溢出，这并不奇怪，事实上 foo 调用 bar，因为这样 bar 需要堆栈帧，bar 然后调用 foo，后者需要堆栈帧，等等。很明显为什么会发生堆栈溢出错误。

我的问题是，如何按原样定义 foo 和 bar 而不会出现堆栈溢出？像Scheme这样的语言允许这个程序，它们会永远运行，是的，但是堆栈不会增长，因为它知道调用后不需要发生任何事情，例如，来自foo的bar，所以不需要保留foo的堆栈帧呼叫酒吧。显然，scala（即 JVM？）确实使堆栈帧保持活动状态。

现在考虑下一个代码示例：

  def foo(): Unit = 
    foo()

  foo()

该程序将永远运行，但永远不会发生堆栈溢出。

我知道 @tailrec 注释，但据我了解，它仅适用于第二个示例之类的情况，但不适用于第一个示例。

有任何想法吗？（我需要第一个示例像第二个示例一样永远运行，而不会出现堆栈溢出。）