C語言或C++語言如何實現尾調用消除？

01-12

不依賴編譯器優化的情況下。實現避免棧溢出的後果。

只能人肉改成循環。方法如下：首先我們有一個尾遞歸程序（assume你知道什麼是尾遞歸，所以不會把這個演算法用在非尾遞歸函數上）

int Fuck(Bitch* bitch) { if (bitch == nullptr) return 0; else return 1 + Fuck(bitch-&>shit); // 我們知道，+是左結合的。 // 所以雖然這個形式不是尾遞歸，但是有等價的寫法。 }

然後我們就可以

在整個函數上加一個while (true)
在遞歸return的地方continue
在非遞歸return的地方break
所有遞歸調用改成對參數的重新賦值。
由於+要改成aggregation的形式，所以我們需要有一個變數來記錄結果。由於0+x == x，所以這個變數的初始值就是0。如果是直接的尾遞歸形式的話，那麼不需要這個變數。

int Fuck(Bitch* bitch) { int screw = 0; while (true) { if (bitch == nullptr) { screw = screw + 0; // 0 break; // return } else { screw = screw + 1; // 1 + bitch = bitch-&>shit; // Fuck(bitch-&>shit) continue; // return } } return screw; }

多簡單啊，然後自己人肉窺孔優化（也就是刪掉一些沒用的廢話）一下就搞定了。

尾遞歸本質上就是GOTO嘛……

#include& #include& int recursion_fac(int); int fake_tail_recursion_fac(int, int); int main(int argNum, char** args) { int n = 1; if (argNum &> 1) n = atoi(args[1]);


    int n1 = recursion_fac(n);

    int n2 = fake_tail_recursion_fac(1, n);

    printf("n1 = %d

", n1);

    printf("n2 = %d

", n2);

    return 0;

}

int recursion_fac(int n) { if (n == 0) return 1; return n * recursion_fac(n - 1); } // fac ret 0 = ret // fac ret n = fac (n*ret) (n-1) int fake_tail_recursion_fac(int ret, int n) { FAC: if (n == 0) return ret; ret = n * ret; n = n - 1; goto FAC; }

我有比輪子哥更好的方法！只是你需要一些FP知識（以及編譯器支持c++11）就好：

--------------------------------2015.7.21更新----------------------------------------

這裡實現了一個Haskell里的until函數，給出終止條件和迭代方式就可以了，表達能力和尾遞歸等效，然而並不需要編譯器有特殊支持。

//c++11 #include & #include & using namespace std;


//until :: (a -&> Bool) -&> (a -&> a) -&> a -&> a

template &

state until(function& p, function& f, state st) {

	for(; not p(st); st = f(st));

	return st;

}
struct FibST {

	int a;

	int b;

	int i;

};
int fib(int n) {

	function& p = [n](FibST st){return st.i == n;};

	function& f = [](FibST st){return FibST {st.b, st.a + st.b, st.i+1};};

	FibST st = until(p, f, FibST {0, 1, 0});

	return st.a;

}

int main() { printf("%d ", fib(10)); return 0; }

------------------------------------2015.7.21更新之前的分割線------------------------------------

代碼如下，fib1是尾遞歸版本的寫法，fib2是改寫之後的樣子。

require "coffee-mate/global"


fib1 = (n) -&>

	iter = (a, b, i) -&>

		if i == n

			return a

		else

			return iter(b, a + b, i + 1)

	return iter(0, 1, 0)
log -&> fib1(10)
fib2 = (n) -&>

	status = iterate (([a, b, i]) -&> [b, a + b, i + 1]), [0, 1, 0]

	return (([a, b, i]) -&> a) (head (dropWhile(([a, b, i]) -&> not (i == n))) status)

log -&> fib2(10)

這裡可以試玩： Try Coffee（可能需要滑鼠在鏈接上停幾秒種再點才能載入出代碼）

可以看到以上代碼fib2中用到了一個iterate函數，這個函數就是來自Haskell的，它很容易實現一個循環版本。我這裡是在JavaScript里實現了一下（當然我用的CoffeeScript）。

於是一來，你只需要實現一些這樣的基礎設施就好了，改寫工作不會更麻煩，只會更簡單。

當然，我這裡的iterate，dropWhile這些函數是基於實現了一套完整的惰性求值的基礎設施的，實際上你寫一個簡化版本很容易，比如可以叫做 iterateWhile，然後把終止條件直接當參數給它，就省去了 dropWhile 這個設施了，然後你只迭代更新一個狀態，就不需要惰性列表的支持了。

思路就是這樣，實現稍後再補，現在應該收拾東東坐火車回家看老婆去了。。。

---------------------------------------下面的統統刪掉！--------------------------------------

寫成尾遞歸（尾調用）的形式，然後在編譯的時候開-O2優化。

以上。

-----------------

額，是看到問題標題進來回答的，看完發現題主在描述里寫了「不依賴編譯器優化」...

關鍵是這麼做沒有實際意義啊，輪子哥是在黑..

然後，我猜測題主是想了解關於尾遞歸的知識所以問的這個問題，其實題主應該問「怎麼把尾遞歸改寫成相應的循環形式」

那麼關於這個問題在我之前關於尾遞歸的回答里舉過很多詳細的例子，所以題主可以找找問題「所有循環都可以寫成尾遞歸么」以及「什麼是尾遞歸」這些問題裡面我的回答，這裡手機不方便貼鏈接...

#include &


template &

struct CallResult

{

    T                              value;

    bool                           success;

    std::function&()&> tailCall;

};
CallResult& FactTail(int n, int a)

{

    CallResult& result;
    if (n &< 0) {
        result.value = 0;
        result.success = true;
        return result;
    }

    if (n == 0) {
        result.value = 1;
        result.success = true;
        return result;
    }

    if (n == 1) {
        result.value = a;
        result.success = true;
        return result;
    }

    result.success  = false;
    result.tailCall = std::bind(FactTail, n - 1, n * a);
    return result;
}

int InvokeFactTail(std::function&()&> func)

{

    CallResult& result = func();

    while (!result.success) {

        result = result.tailCall();

    }

    return result.value;

}

int main() { std::function&()&> func = std::bind(FactTail, 5, 1); printf("%d", InvokeFactTail(func)); getchar(); return 0; }

拿走，不謝，例子用的百度百科-尾遞歸的例子。