遞歸都可以用非遞歸代替嗎？

答案: 并一定. 但是 遞歸算法一定可以轉換成為非遞歸算法, 有些可以用循環解決, 有些復雜的遞歸是不行的, 一般用棧來解決.遞歸算法向非遞歸算法轉換摘自:遞歸算法和非遞歸算法的區別和轉換 遞歸算法實際上是一種分而治之的方法，它把復雜問題分解為簡單問題來求解。對于某些復雜問題(例如hanio塔問題)，遞歸算法是一種自然且合乎邏輯的解決問題的方式，但是遞歸算法的執行效率通常比較差。因此，在求解某些問題時，常采用遞歸算法來分析問題，用非遞歸算法來求解問題；另外，有些程序設計語言不支持遞歸，這就需要把遞歸算法轉換為非遞歸算法。 將遞歸算法轉換為非遞歸算法有兩種方法，一種是直接求值，不需要回溯；另一種是不能直接求值，需要回溯。前者使用一些變量保存中間結果，稱為直接轉換法；后者使用棧保存中間結果，稱為間接轉換法，下面分別討論這兩種方法。1. 直接轉換法 直接轉換法通常用來消除尾遞歸和單向遞歸，將遞歸結構用循環結構來替代。 尾遞歸是指在遞歸算法中，遞歸調用語句只有一個，而且是處在算法的最后。例如求階乘的遞歸算法： long fact(int n) { if (n==0) return 1; else return n*fact(n-1); } 當遞歸調用返回時，是返回到上一層遞歸調用的下一條語句，而這個返回位置正好是算法的結束處，所以，不必利用棧來保存返回信息。對于尾遞歸形式的遞歸算法，可以利用循環結構來替代。例如求階乘的遞歸算法可以寫成如下循環結構的非遞歸算法： long fact(int n) { int s=0; for (int i=1; i<=n;i++) s=s*i; //用s保存中間結果 return s; } 單向遞歸是指遞歸算法中雖然有多處遞歸調用語句，但各遞歸調用語句的參數之間沒有關系，并且這些遞歸調用語句都處在遞歸算法的最后。顯然，尾遞歸是單向遞歸的特例。例如求斐波那契數列的遞歸算法如下： int f(int n) { if (n= =1 | | n= =0) return 1; else return f(n-1)+f(n-2); } 對于單向遞歸，可以設置一些變量保存中間結構，將遞歸結構用循環結構來替代。例如求斐波那契數列的算法中用s1和s2保存中間的計算結果，非遞歸函數如下： int f(int n) { int i, s; int s1=1, s2=1; for (i=3; i<=n; ++i) { s=s1+s2; s2=s1; // 保存f(n-2)的值 s1=s; //保存f(n-1)的值 } return s; }2. 間接轉換法 該方法使用棧保存中間結果，一般需根據遞歸函數在執行過程中棧的變化得到。其一般過程如下： 將初始狀態s0進棧 while (棧不為空) { 退棧，將棧頂元素賦給s; if (s是要找的結果) 返回; else { 尋找到s的相關狀態s1; 將s1進棧 } } 間接轉換法在數據結構中有較多實例，如二叉樹遍歷算法的非遞歸實現、圖的深度優先遍歷算法的非遞歸實現等等。 使用非遞歸方式實現遞歸問題的算法程序,不僅可以節省存儲空間,而且可以極大地提高算法程序的執行效率。本文將遞歸問題分成簡單遞歸問題和復雜遞歸問題;簡單遞歸問題的非遞歸實現采用遞推技術加以求解,復雜遞歸問題則根據問題求解的特點采用兩類非遞歸實現算法,使用棧加以實現。