Longest common subsequence This is what I code while reading http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

basic_lcs.js

//Without memoization. This can be very slow
function basic_lcs_count (x, y) {
	function rec(i,j){
		if (i===0||j===0) return 0;
		if (x[i-1]===y[j-1]) return rec(i-1,j-1)+1;
		else return Math.max(rec(i,j-1),rec(i-1,j));
	}
	return rec(x.length,y.length);
}

function basic_lcs (x, y) {
	function rec(i,j){
		if (i===0||j===0) return "";
		if (x[i-1]===y[j-1]) return rec(i-1,j-1)+x[i-1];
		else {
			var rj=rec(i,j-1), ri=rec(i-1,j);
			return (rj.length>ri.length)?rj:ri;
		}
	}
	return rec(x.length,y.length);
}

//with memoization
function lcs (x, y) {
	//memoization array
	for(var memo=[],i=0;i<=x.length;i++)memo[i]=[];

	function rec(i,j){
		var ret = memo[i][j];
		if (ret === undefined){
			if (i===0||j===0) ret = "";
			else if (x[i-1]===y[j-1]) ret = rec(i-1,j-1)+x[i-1];
			else {
				var rj=rec(i,j-1), ri=rec(i-1,j);
				ret = (rj.length>ri.length)?rj:ri;
			}
			memo[i][j] = ret;
		}
		return ret;
	}
	return rec(x.length,y.length);
}