How to make recursive function on javascript without Maximum call stack size exceeded error?

Question

I would like to make the same robot walk function with javascript but it get call stack size error.

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));

The xpected output in the link is all the possible combinations to travel a given distance - however, this code outputs a single value, so is not even close to the requirement — Jaromanda X
– Jaromanda X, Commented Aug 12, 2017 at 6:40
if the answer below is correct (and it does look correct) - then your output would be 1.803963808151009e+26 lines of combinations - how much time do you have? — Jaromanda X
– Jaromanda X, Commented Aug 12, 2017 at 6:50
sorry about the misunderstanding. Yes, you are right. The variable "count" means "How many walk pattern would be to walk 100 meters" — user76333
– user76333, Commented Aug 12, 2017 at 7:06

marvel308 · Accepted Answer · 2017-08-12 06:37:48Z

1

It would exceed call stack size since your complexity is exponential, you can use memoization to solve your problem which helps covert an exponential time complexity into a polynomial one, now this code runs in 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));

answered Aug 12, 2017 at 6:37

marvel308

10.5k3 gold badges24 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

guest271314 Over a year ago

How do we know what expected result is?

marvel308 Over a year ago

you can try verfiying for smaller values, only OP can verify for 100 though

Collectives™ on Stack Overflow

How to make recursive function on javascript without Maximum call stack size exceeded error?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related