はエラーを超えましたか？

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）

結果が期待される何

\t let obj = {}; 
 
\t function walk(meter) { 
 
     if(meter < 0) { 
 
      count = 0; 
 
     } 
 
     else if(obj[meter] != undefined){ 
 
     \t 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));