新手求教，请问递归进行双递归应该怎么理解 - 编程论坛

#2

Sv少2020-03-19 13:26

第一次就当做树根，然后每次往左分树枝，count == 0或1是树枝末端，每向上一节就把给直接的左边树枝补全。就是二叉树

#3

lidepeng19952020-03-19 13:34

回复 2楼 Sv少

谢谢大佬的回复，不过您讲的太深奥了，不明白就打count=4，是怎么个入建出建的过程

#4

return_02020-03-19 19:10

你这个，会运行超时，如果掌握了桶的话可以减少计算

#5

return_02020-03-19 19:12

这个剪枝很简单：

程序代码：

#include<bits/stdc++.h>
using namespace std;
int x[10010]={0};
int f(int n){
    if(n<=1)return 1;
    if(x[n]!=0){
        return x[n];

    }
    x[n]=f(n-1)+f(n-2);
    return f(n-1)+f(n-2);
}
int main(){
    int n;
    cin>>n;
    cout<<f(n);
    return 0;
}

对照代码就行了

#6

forever742020-03-19 19:14

大多数情况下，递归就是数学归纳法，所以回去深刻理解数学归纳法吧，再抽空从哲学高度总结一下。
回来以后递归就都不算事儿了。

#7

return_02020-03-19 19:18

回复楼主 lidepeng1995

当然，你初学算法肯定会懵的，我也一样，递归这个东西，说白了就是函数套用函数自身，本身其实是一种基础的算法结构，到了后面，你会学到更多琐碎的算法，如深搜和广搜，都用到了递归结构。当然，在没有return的情况下，这个函数理所当然可以多次套用自身。
还有，桶这个东西最多就是用来剪枝，避免运行超时，否则你的这一段代码，面向大多数更多的题目数据，应该会超时，这也是我第一次写这个代码时所犯的错误。希望上面内容对你有用。。。

#8

lin51616782020-03-20 10:56

回复 5楼 return_0

真考虑效率
这个题目根本不应该递归
就算递归也应该是一路递归而不是两路
两路加剪枝还不如一路递归处理

#9

Sv少2020-03-20 13:25

           4                               F0
      3        2                     F1           F6
   2    1     1   0               F2     F5     F7    F8
1  0                         F3    F4

  1+0
   1  +  1    1 + 0
      2    +    1
            3
差不多就是这样，上面是count的值变化和运行顺序，下面是返回值得变化，最终返回3.count往下分叉等count=1或0时开始结束分叉，开始返回相应的结果。分叉时优先往左边分，符合if条件时就不能分了，就有返回值1。

#10

lidepeng19952020-03-21 13:07

刚学算法算法确实懵，四楼给的代码正在看，希望有一天可以看懂，6楼说的很好，归纳我了解的并不深，深入学习是应该的，
八楼是在回答我的问题吗？还是4楼的问题？不过还是谢谢
九楼的给的例子很明白，感谢

#11

lidepeng19952020-03-21 15:11

   4                     1          5
      3        2         1       4               3
                         1      3       2      2         1
   2    1     1   0      1    2   1   1   0     1 0
1  0                    1   1    0
                         1
  1+0                    1
   1  +  1    1 + 0      1     1+0+1+1   +    1+0+1      结果5

      2    +    1        1  不知道我的理解对吗
            3            1