在我看来,在C和C++中进行尾递归优化是完美的,但是在调试时我似乎永远不会看到表示此优化的帧堆栈.这有点好,因为堆栈告诉我递归的深度.但是,优化也会很好.
是否有任何C++编译器进行此优化？为什么？为什么不？
我如何告诉编译器这样做？
/O2或/Ox-O2或-O3如何在某种情况下检查编译器是否已完成此操作？
我仍然会建议如何确定编译器是否对某个函数进行了优化(尽管我发现它让人放心,Konrad告诉我假设它)
总是可以通过进行无限递归来检查编译器是否完成此操作,并检查它是否导致无限循环或堆栈溢出(我用GCC做了这个并且发现这-O2已经足够了),但我想成为能够检查我知道的某个功能无论如何都会终止.我很想有一个简单的方法来检查这个:)
经过一些测试,我发现析构函数破坏了进行优化的可能性.有时可能值得更改某些变量和临时值的范围,以确保它们在return语句开始之前超出范围.
如果在尾调用后需要运行任何析构函数,则无法进行尾调用优化.
我正在阅读关于尾递归的这篇文章.
我将复制发布的解决方案:
unsigned int f( unsigned int a ) {
if ( a == 0 ) {
return a;
}
return f( a - 1 ); // tail recursion
}
我想知道,如果结果取决于几个递归函数调用呢？例如:
unsigned int f( unsigned int a ) {
if ( a == 0 ) {
return a;
}
return f(a -1) + f( a - 1 );
}
上面的代码会被编译器优化吗？
假设我有一个以递归方式访问的结构。
伪代码：
visit(node n)
{
if (n == visited)
return;
//do something
setVisited(n);
foreach child_node in n.getChildren(){
visit(child_node);
}
}
根据这个线程尾递归可以在以下情况下发生：
尾递归基本上是在以下情况下：
- 只有一个递归调用
- 该调用是函数中的最后一条语句
在上面的伪代码中，递归调用是最后一条语句，但由于调用发生在循环内，因此存在多个递归调用。我猜编译器无法检测到尾递归。
我的问题是：
无论如何重构上面的代码以使其尾递归？我正在寻找一种不会删除递归的解决方案，如果有的话（例如，我不想使用堆栈来模拟递归并将其转换为迭代函数）。
这可能吗？
如果语言是相关的，我正在使用 C++。
我在下面有以下代码,它解析文本文件并索引单词和行:
bool Database::addFromFileToListAndIndex(string path, BSTIndex* & index, list<Line *> & myList)
{
bool result = false;
ifstream txtFile;
txtFile.open(path, ifstream::in);
char line[200];
Line * ln;
//if path is valid AND is not already in the list then add it
if(txtFile.is_open() && (find(textFilePaths.begin(), textFilePaths.end(), path) == textFilePaths.end())) //the path is valid
{
//Add the path to the list of file paths
textFilePaths.push_back(path);
int lineNumber = 1;
while(!txtFile.eof())
{
txtFile.getline(line, 200);
ln = new Line(line, path, lineNumber);
if(ln->getLine() != "")
{
lineNumber++; …使编译器生成尾递归代码似乎是一个简单的想法.但是大多数常用语言编译器(包括C和Pascal)都没有这样做,因此这些语言不能仅仅根据过程调用来表示迭代过程.这些语言中尾递归的难点在于它们的实现使用堆栈来存储过程参数和局部变量以及返回地址.
我无法理解为什么如果将堆栈用于过程参数,局部变量和返回地址,则无法实现尾递归.
我试图使该函数尾部递归，以便我可以使用它来处理大量事件而不会导致堆栈溢出。我确保将递归调用放在函数的最后一行，但是它仍然使递归调用充满了调用堆栈。
我还需要做些其他事情来使其尾部递归，还是我的编译器不知道如何对其进行优化？
我应该放弃此功能，而是使用循环吗？
template <class Csi>
void GetEvents(EventHandle handle, vector<int> desiredCodes, vector<EventHandle> &events, Csi &csi)
{
if (handle == INVALID_HANDLE)
{
return;
}
int code = csi.GetEventCode(handle);
bool codeSatisfiesSearch = (find(desiredCodes.begin(), desiredCodes.end(), code) != desiredCodes.end());
if (codeSatisfiesSearch)
{
events.push_back(handle);
handle = csi.FindNextEventEx(handle, &desiredCodes[0], 0, desiredCodes.size());
}
else
{
handle = csi.FindNextEventEx(handle, &desiredCodes[0], 0, desiredCodes.size());
}
return GetEvents(handle, desiredCodes, events, csi);
}
作为C++的新手,我想知道在使用递归时是否有特定的事情需要考虑,因为与Python,Java和/或函数语言等语言相比,语言的特异性和低级别性.
另外,我想知道各种编译器在处理递归方面是否存在很多差异(特别是关于尾递归).我目前在CodeBlocks和VS2010上使用gcc.
我正在阅读尾递归和传统递归之间的区别,并发现它提到"Tail Recursion然而是一种不使用任何堆栈空间的递归形式,因此是一种安全使用递归的方法."
我很难理解如何.
使用Traditional和tail递归比较数字的发现阶乘
传统的递归
/* traditional recursion */
fun(5);
int fun(int n)
{
if(n == 0)
return 1;
return n * fun(n-1);
}
这里,调用堆栈看起来像
5 * fact(4)
|
4 * fact(3)
|
3 * fact(2)
|
2 * fact(1)
|
1 * fact(0)
|
1
尾递归
/* tail recursion */
fun(5,1)
int fun(int n, int sofar)
{
int ret = 0;
if(n == 0)
return sofar;
ret = fun(n-1,sofar*n);
return ret;
}
然而,即使在这里,变量'sofar'将在不同点保持 - 5,20,60,120,120.但是一旦从递归调用#4的基本情况调用return,它仍然必须返回120到递归调用#3,然后返回到#2,#1并返回到main.所以,我的意思是说使用堆栈并且每次返回上一次调用时,都可以看到该时间点的变量,这意味着它在每一步都被保存.
除非,尾递归写得如下,我无法理解它是如何节省堆栈空间的.
/* tail recursion …int f(int n, int mul) {
if (abs(n)%mul == 0) return n;
else return f(n - 1, mul);
}
所以它向下舍入到下一个mul.但显然对n的大值不好.如何安全有效地表达？
编写下面的代码来计算前70个斐波纳契数.我有两个问题:
1)为什么程序对于每个连续的值变得越来越慢i？是因为调用具有高数字的函数会导致大量内存占用.
2)我可以使用什么技术或编码方案来加速运行时的程序计算？
#include <iostream>
int fib(int n) {
if (n == 1 || n == 2) return 1;
return fib(n - 1) + fib(n - 2);
}
void main() {
for (int i = 1; i<70; i++)
cout << " fib(" << i << ") = " << fib(i) << endl;
}
我有一门功课，我应该等到我写控制台“停止”一次又一次地做一些动作，但我不能使用for，while，goto，switch，[]，typedef在我的所有代码。那么如何更换循环呢？