部分尾递归函数是否仍然可以获得完全尾递归函数的优化优势？

Question

我意识到这个问题的答案可能会因不同的语言而异，而我最感兴趣的语言是C++。如果标签需要更改，因为这不能用与语言无关的方式回答，请随时取消。

---

是否有可能有一个函数是部分尾递归，并仍然有任何优势，尾递归会得到你？

据我所知，尾递归不是完成一个完整的函数调用，编译器会优化函数，只是将参数更改为新参数并跳转到函数的开头。

如果你有这样的功能：

def example(arg): 
    if arg == 0: 
     return 0 # base case 

    if arg % 2 == 0: 
     return example(arg - 1) # should be tail recursive 

    return 3 + example(arg - 1) # isn't tail recursive because 3 is added to the result 

当优化器遇到类似的东西（其中函数是尾递归在某些情况下，而不是在其他人）将它打开一进一出jump而另一个变成call，或者将一些优化现实的事实（如果我知道它我不会问），它必须把所有变成call，并且失去了如果函数是尾随函数时会产生的所有效率，递归？

Answer 1

在流程，当我想到尾调用的，想到的第一语言，第二种情况是保证由语言规范尾调用。 （术语注：最好是将此类函数调用为“尾调用”。）

该计划规范定义到底是什么尾调用都在计划和任务是编译器支持他们特别。你可以在11.20中看到定义。尾部呼叫和尾部背景 R RS（source）。

请注意，在Scheme中，规范没有说明优化尾部调用。相反，它表示实现必须支持无限数量的活动尾调用 - 语言运行时的语义属性。它们可以作为普通调用来实现，但通常不会。

例如，在C：

把你的例子的C版。

int example(int arg) 
{ 
    if (arg == 0) 
     return 0; 
    if ((arg % 2) == 0) 
     return example(arg - 1); 
    return 3 + example(arg - 1); 
} 

使用gcc的常用优化设置（-O2）i386的编译：

_example: 
    pushl %ebp 
    xorl %eax, %eax 
    movl %esp, %ebp 
    movl 8(%ebp), %edx 
    testl %edx, %edx 
    jne L5 
    jmp L15 
    .align 4,0x90 
L14: 
    decl %edx 
    testl %edx, %edx 
    je L7 
L5: 
    testb $1, %dl 
    je L14 
    decl %edx 
    addl $3, %eax 
    testl %edx, %edx 
    jne L5 
L7: 
    leave 
    ret 
L15: 
    leave 
    xorl %eax, %eax 
    ret 

注意，有在汇编代码中没有函数调用。海湾合作委员会不仅将您的尾巴呼叫优化为跳跃，还将非尾巴呼叫优化为跳跃。

Answer 2

据我了解，一个聪明的编译器可以通过只跳到例子切入点，而不是建立一个新的堆栈帧适用尾递归到你的第一个电话。下面的返回将把堆栈展开给原来的调用者，即使它不能为另一个调用做到这一点，也能有效地“结束”两个调用。

而你可以通过移动的3里面调用的加入优化功能：

def example(arg, add=0): 
    arg += add 
    .... 
    return example(arg - 1, 3) # tail now too 

另一种方法是创建第二个功能，同时具有相互调用。

我不知道是否Python或C++编译器就可以搞定，虽然，但你可以检查装配输出C++。奇怪的是我认为检查python的字节码输出可能会更困难。