宿題だか課題だか知らないが、末尾再帰はループに置き換えることができます。
Wikipediaによりますと、
/* 変換前 */
T_0 func (T_1 a_1,T_2 a_2,..., T_n a_n ) {
P
return func(na_1 , na_2 ... na_n);
}
この形をした(末尾)再帰は:
/* 変換後 */
T_0 func (T_1 a_1,T_2 a_2,..., T_n a_n ) {
while (1) {
P
T_1 nTmp_1 = na_1;
T_2 nTmp_2 = na_2;
:
T_n nTmp_n = na_n;
a_1=nTmp_1;
a_2=nTmp_2;
:
a_n=nTmp_n;
}
}
/* T_i は型、P は手続き、na_i は式を表す。それ以外の識別子は変数を表す。
* Pの中に最低1個のreturn文がないと無限ループあるいはスタックオーバーフローになる。
*/
...だってさ。
再帰関数であまりに有名な階乗(factorial)についてやってみましょ。
/* 元ネタ */
int fact(int n) {
if ( n == 0 ) return 1;
return n * fact(n-1);
}
こいつを上記 変換前 の形に整形します。
int fact_(int x, int n) {
if ( n == 0 ) return x; // ここが P に相当
return fact_(x*n, n-1); // 末尾再帰
}
int fact(int n) {
return fact_(1,n);
}
んでもって 変換後 にあるルールで変換します。
#include <iostream>
int fact_(int x, int n) {
while ( true ) {
if ( n == 0 ) return x;
int nTmp_1 = x*n;
int nTmp_2 = n-1;
x = nTmp_1;
n = nTmp_2;
}
}
inline int fact(int n) {
return fact_(1,n);
}
int main() {
std::cout << fact(4) << std::endl;
}
おー、できたできた。