如何使javascript上的递归函数没有最大调用堆栈大小超过错误？

Question

我想用javascript做同样的机器人行走功能，但它得到了调用堆栈大小错误。

http://www.chegg.com/homework-help/questions-and-answers/robot-take-steps-1-2-3-meters-write-program-allows-shows-possible-steps-robot-take-using-r-q3756383

    function walk(meter) {
        if(meter < 0) {
            count = 0;
        } else if(meter <= 2) {
            count = meter;
        } else if(meter == 3) {
            count = walk(meter-1)+walk(meter-2)+1;
        } else {
            count = walk(meter-1)+walk(meter-2)+walk(meter-3);
        }
        return count;
    }


    console.log(walk(100));

Answer 1

它会超过调用堆栈的大小因为你的复杂度是指数的，你可以使用记忆法来解决你的问题，这有助于将指数时间复杂度转换为多项式复杂度，现在这段代码运行在O(100)。

​

	let obj = {};
	function walk(meter) {
        if(meter < 0) {
            count = 0;
        }
        else if(obj[meter] != undefined){
        	return obj[meter];
        } else if(meter <= 2) {
            count = meter;
        } else if(meter == 3) {
            count = walk(meter-1)+walk(meter-2)+1;
        } else {
            count = walk(meter-1)+walk(meter-2)+walk(meter-3);
        }
        obj[meter] = count;
        return count;
    }


    console.log(walk(100));

​