C++でCPS

C++11からはラムダ式が導入され、CPS(Continuation Passing Style; 継続渡しスタイル)で簡単に記述できるようになった（と思う）。実用性の程はともかく。

#include <functional>
#include <iostream>

// 階乗計算
int fact(int n)
{
  if (n == 0)
    return 1;
  else
    return n * fact(n - 1);
}

// 階乗計算/CPS
void fact_cps(int n, std::function<void(int)> k)
{
  if (n == 0)
    k(1);
  else
    fact_cps(n - 1, [n,&k](int r){ k(n * r); });
}

// フィボナッチ数
int fib(int n)
{
  if (n <= 2)
    return 1;
  else
    return fib(n - 1)
           + fib(n - 2);
}

// フィボナッチ数/CPS
void fib_cps(int n, std::function<void(int)> k)
{
  if (n <= 2)
    k(1);
  else
    fib_cps(n - 1, [n,&k](int r1){
      fib_cps(n - 2, [r1,&k](int r2){ k(r1 + r2); }); });
}

int main()
{
  std::cout << fact(5) << std::endl;
  fact_cps(5, [](int r){ std::cout << r << std::endl; });

  std::cout << fib(10) << std::endl;
  fib_cps(10, [](int r){ std::cout << r << std::endl; });
}

メモ：上記コードでは、組み込み型(int)への参照と継続kのコピー回避のため、ラムダ式の変数キャプチャを個別指定しているが、単に[&]または[=]指定でも正常動作する。