Recursion and memoization

factorial.cpp

unsigned factorial(unsigned n)
{
    if(n==0)
        return 1;
    else
        return n*factorial(n-1);
}

fibo.cpp

unsigned fibo(unsigned n)
{
    if(n<=1)
        return n;
    return fibo(n-1)+fibo(n-2);
}

fibo_memo.cpp

unsigned fibo_memo(unsigned n)
{
	static map<unsigned,unsigned> memo;
	if(n<=1)
		return n;
	if(memo.count(n)>0)
		return memo[n];
	// otherwise
	unsigned ret=fibo_memo(n-1)+fibo_memo(n-2);
	memo[n]=ret;
	return ret;
}

main.cpp

int main(int argc, char*argv[])
{
    fibo1=memoize(fibo1);
    cout << argv[1] << " ->" << fibo1(atoi(argv[1])) << endl;
}

memo1.cpp

std::function<unsigned(unsigned)> fibo1=[](unsigned n)
{
	if(n<=1)
    	return n;
	return fibo1(n-1)+fibo1(n-2);
};

memoize.cpp

template<class InType, class OutType>
std::function<OutType(InType)> memoize(std::function<OutType(InType)> foo)
{
	// return a lambda, this is a function
	return [foo](InType n){
		static map<InType,OutType> memo;

		OutType ret;
		if(memo.count(n)>0) {
			ret =memo[n];
			return ret;
		}
		ret=foo(n);
		memo[n]=ret;
		return ret;
	};
}