求教递归问题？

Question

有个逻辑题，给出总数楼梯，每次最多可走3步楼梯
如： 总数楼梯3步
有如下：

1 1 1
1 2 
2 1
3

请问用js如何实现这样的递归？

-----补充---

这个数组有点看不懂，第一个显示3，但length有7，这是为什么呢？希望解答下，还有其余三个。

Answer 1

随手写了一个：

"use strict";

function getAns(n) {
  let ans = [];
  let res = [];

  for (let i = 1; i <= 3; i++) {
    res = [i];
    dfs(i);
  }

  function dfs(sum) {
    if (sum === n) {
      ans.push(res.concat());
      return;
    }

    if (sum > n)
      return;

    for (let i = 1; i <= 3; i++) {
      res.push(i);
      dfs(sum + i);
      res.pop();
    }
  }

  return ans;
}

var ans = getAns(3);
console.log(ans);
// [ [ 1, 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 3 ] ]

如果楼主对这类题感兴趣的话，建议做下 leetcode，强推一发我的 leetcode repo https://github.com/hanzichi/l... ps：代码还可以用 memoize 进行优化，留给楼主自己了

更新：还是建议楼主先去了解下 深度优先搜索 吧，不然看了也没用 ..

Answer 2

0 function dfs(n, arr) {
1   for (var i = Math.min(n, 3); i > 0; i--) {
2     arr.push(i);
3     if (n - i > 0) dfs(n - i, arr);
4     else document.write(arr + '<br/>');
5     arr.pop();
6   }
7 }
8 dfs(4, []);

arr 是个临时列表 保存一种组合情况用的 必须在函数调用的外面创建 不能在递归函数里创建

就拿我最下面那个4的例子把程序跑一遍

1. 第8行 开始调用dfs(4, [])

2. 第1行 n=4 i=3 arr=[]

3. 第2行 n=4 i=3 arr=[3]

4. 第3行 递归调用dfs(4-3, [3])

5. 第1行 n=1 i=1 arr=[3]

6. 第2行 n=1 i=1 arr=[3,1]

7. 第3行 n-i>0不成立 不再递归

8. 第4行 打印arr([3,1])

9. 第5行 把arr最后一个元素删掉 arr=[3]

10. 第1行 n=1 i=0 arr=[3] 退出循环 递归终止

11. 第5行 把arr最后一个元素删掉 arr=[]

12. 第1行 n=4 i=2 arr=[]

13. 第2行 n=4 i=2 arr=[2]

14. 第3行 递归调用dfs(4-2, [2])

15. 第1行 n=2 i=2 arr=[2]

16. 第2行 n=2 i=2 arr=[2,2]

17. 第3行 n-i>0不成立 不再递归

18. 第4行 打印arr([2,2])

19. 第5行 把arr最后一个元素删掉 arr=[2]

20. 第1行 n=2 i=1 arr=[2]

21. 第2行 n=2 i=1 arr=[2,1]

22. 第3行 递归调用dfs(2-1, [2,1])

23. 第1行 n=1 i=1 arr=[2,1]

24. 第2行 n=1 i=1 arr=[2,1,1]

25. 第3行 n-i>0不成立 不再递归

26. 第4行 打印arr([2,1,1])

27. 第5行 把arr最后一个元素删掉 arr=[2,1]

28. 第1行 n=1 i=0 arr=[2,1] 退出循环 递归终止

...

Answer 3

真心不知道为啥被踩了，还一个评论都没有-_-

下面的php代码可能有点“误导性”，$r在一开始的地方忘记删除了，如果你仿照这个php代码用js写，可能会在 r 这里导致变量“污染”的问题。给你看个js的代码吧:

    <script type="text/javascript">
      var steps = [1,2,3];
      function step(floors,steps){
        let r = new Array();
        if(floors == 0)
          return true;
        if(floors <0)
          return false;
        for(a in steps){
          r[steps[a]] = step(floors-steps[a],steps);
        }
        return r;
      }
      console.log(step(3,steps));
    </script>

运行结果

---

来一段php的代码吧 js的不太熟悉，结果我看没问题。

结果：
array(3) {
  [1]=>
  array(3) {
    [1]=>
    array(3) {
      [1]=>
      bool(true)
      [2]=>
      bool(false)
      [3]=>
      bool(false)
    }
    [2]=>
    bool(true)
    [3]=>
    bool(false)
  }
  [2]=>
  array(3) {
    [1]=>
    bool(true)
    [2]=>
    bool(false)
    [3]=>
    bool(false)
  }
  [3]=>
  bool(true)
}

代码：

<?php
$steps = [1,2,3];
function steps($floors,$steps){
    if($floors <0)
        return false;
    if($floors == 0)
        return true;
    foreach($steps as $key => $value){
        $r[$value] = steps($floors-$value,$steps);
    }
    return $r;
}
var_dump(steps(3,$steps));