再帰をスタック構造を利用してループに変更する。

再帰をスタックに直したことが無かったので、 factorial と fibonacci について実行してみた。（ factorial(0) が正しく動かないのは見逃してください。）

#include <iostream>
#include <stack>
using namespace std;

int factorial(int n){
    int ans = 1;
    stack<int> s;
    s.push(n);

    while(! s.empty()){
        int x = s.top();
        s.pop();
        ans *= x;
        if(x > 1){
            s.push(x - 1);
        }
    }

    return ans;
}

int fibonacci(int n){
    int ans = 0;
    stack<int> s;
    s.push(n);

    while(! s.empty()){
        int x = s.top();
        s.pop();
        if(x < 2){
            ans += x;
        }else{
            s.push(x - 1);
            s.push(x - 2);
        }
    }

    return ans;
}

int main(){
    cout << factorial(10) << endl;
    cout << fibonacci(11) << endl;
    return 0;
}

実行結果

3628800
89

これでもうまく動作して入るが、このプログラムの factorial は、下記に並べる前者のコードより、後者のコードに近い。

int factorial(int n){
  if(n < 1){
    return 1;
  }else{
    return n * factorial(n - 1);
  }
}

このプログラムでは、 factorial(10) = (10 * (9 * (8 * (7 * (6 * (5 * (4 * (3 * (2 * (1)))))))))) と計算する。

int ans;

int factorial(int n){
  ans = 1;
  sub(n);
  return ans;
}

void sub(int n){
  ans *= n;
  if(n > 1){
    sub(n - 1);
  }
}

このプログラムでは、 factorial(10) = 1 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 と計算する。

再帰を正しくスタックを用いたループに変更するならば、アセンブリの挙動を真似れば良い。
以前フィボナッチ数列を Power PC アセンブリで書いたことがあるので、それを思い出せば綺麗なプログラムが書けそうだから、もう一度アセンブリプログラミングを復習しておきます。