階乗計算

言語が提供するコールスタックを利用せずに再帰の要領で計算したくなった。特にオチは無い。

using System;
using System.Collections.Generic;

class App
{
  static public void Main(string[] args)
  {
    const int N = 6;

    /////////////////////////////////////
    // 6!=720 を、3つの方法でやってみた。
    /////////////////////////////////////

    // 1. 素朴にループで
    Console.WriteLine(Fact1(N));

    // 2. 素朴に再帰で
    Console.WriteLine(Fact2(N));

    // 3. コールスタックを自前で用意して再帰っぽく
    Console.WriteLine(Fact3(N));
  }

  // 素朴にループ
  static int Fact1(int n)
  {
    int prod = 1;
    for (int i = 0; i < n; i++)
    {
      prod *= (i + 1);
    }
    return prod;
  }

  // 素朴に再帰
  static int Fact2(int n)
  {
    if (n == 0) return 1;
    return n * Fact2(n - 1);
  }

  // コールスタックに積まれる情報
  class Frame
  {
    public int Arg { get; set; }
    public int Ret { get; set; }
    public Frame(int arg) { Arg = arg; }
  }

  // C#が提供するコールスタックを使わず
  // スタックを自前で用意
  static int Fact3(int n)
  {
    // なんちゃってコールスタック
    Stack<Frame> frames = new Stack<Frame>();

    Frame f = new Frame(n);
    while(true)
    {
      if (f.Arg == 0)
      {
        // 再帰の出口
        f.Ret = 1;
        break;
      }
      else
      {
        // 再帰呼び出し
        frames.Push(f);
        f = new Frame(f.Arg - 1);
      }
    }

    // 残りの掛け算
    while (0 < frames.Count)
    {
      Frame peek = frames.Peek();
      peek.Ret = f.Ret * peek.Arg;
      f = frames.Pop();
    }
    return f.Ret;
  }
}

動かしてみた。ちゃんと動いてるっぽい。