学步园

好久没写手快生了。好久没来也已是物是人非了。发个阶乘的尾递归、CPS等几种写法吧。

#include "stdafx.h"

// 阶乘

#include <iostream>
#include <functional>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	function<int(int)> Fact = [&Fact](int n) -> int {
		if (n == 1) return 1;
		else return n * Fact(n - 1);
	};
	
	function<int(int)> FactTail = [](int n) -> int {
		function<int(int, int)> SubRoutine = [&](int n, int state) -> int {
			if (n == 1) return 1 * state;
			else return SubRoutine(n - 1, n * state);
		};
		return SubRoutine(n, 1);
	};

	function<int(int)> FactCPS = [](int n) -> int {
		function<int(int, function<int(int)>)> SubRoutine = [&](int n, function<int(int)> cont) -> int {
			if (n == 1) return cont(1);
			else return SubRoutine(n - 1, [&](int result) { return cont(n * result); });
		};
		return SubRoutine(n, [](int x){ return x; });
	};

	function<int(int)> FactCpsWithState = [](int n) -> int {
		function<int(int, int, function<int(int)>)> SubRoutine = [&](int n, int state, function<int(int)> cont) -> int {
			if (n == 1) return cont(1 * state);
			else return SubRoutine(n - 1, n * state, cont);
		};
		return SubRoutine(n, 1, [](int x){ return x; });
	};
	
	cout << "原始阶乘算法，10 的阶乘值为：" << Fact(10) << endl;
	cout << "尾递归阶乘算法，10 的阶乘值为：" << FactTail(10) << endl;
	cout << "CPS阶乘算法，10 的阶乘值为：" << FactCPS(10) << endl;
	cout << "带状态CPS阶乘算法，10 的阶乘值为：" << FactCpsWithState(10) << endl;

    return 0;
}