搞明白递归

摘自帅地学编程

递归三大要素

• 明晰这个函数的用处
  • 函数的功能，达到什么目的

• 寻找递归结束的条件

  • 找出递归的结束条件（当参数为傻时，递归结束，之后直接把结果返回）

    int f(int n){
        if(n==1){
            return 1;
        }
    }

• 找出函数的等价关系

  • 不断缩小参数的范围，如:f(n)=n*f(n-1)

    int f(int n){
        if(n<=2){
            return n;
        }
        return f(n-1)*n;
    }

例题

反转链表递归（不大懂，循环法√）

递归->递推

递归是从上往下递归的，直到递归到最底，再一层一层返回。

• eg:f(3)=f(2)+f(1)

  public int f(int n){
    if(n<=2)
      return n;
    int f1=1;
    int f2=2;
    int sum=0;
  
    for (int i=3;i<=n;i++){
      sum=f1+f2;
      f1=f2;
      f2=sum;
    }
    return sum;
  }