递归入门与优化 + 例题🌟🌟🌟🌟🌟

课程_算法系统课 0 238 免费

递归入门

递归三部曲

第一要素：明确你这个函数想要干什么

//1.计算n!
int f(int n){

}

第二要素：寻找递归结束条件

//计算n!
int f(int n){
  if(n <= 1){
    return 1;
  }

}

第三要素：找出函数的等价关系式

f(n) =f(n-1) * n;

//计算n!
int f(int n){
  if(n <= 1){
    return 1;
  }
  return f(n-1) * n;
}

案例1：斐波那契数列

斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34….，即第一项 f(1) = 1,第二项 f(2) = 1…..,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。

//1.f(n)表示第n项的值
int f(int n){
  if(n <= 2){
    return 1;
  }

  //3.关系式
  return f(n-1) + f(n-2);
}

案例2：小青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

//1.功能：f(n)
int f(int n){
  //2.递归介绍条件
  if(n <= 2){
    return n;
  }
  //3.关系式
  return f(n-1) + f(n-2);
}

要跳上第 n 个台阶，青蛙只能从第 n – 1 个台阶跳，或者从第 n – 2 个台阶跳。或的关系

f(n) = f(n-2) + f(n-1);

字节真题：仅用反转栈（非常重要）

PS：我希望大家通过这道题，能够用整体的方法去分析递归，这就是这道题最大的目的！

        //-------------- 方法1-----------------------
       // stack = 1,2,3,4,5=> stack = 5,4,3,2,1
    public static Stack<Integer> reverse(Stack<Integer> stack){
        //结束条件
        if(stack.isEmpty() || stack.size() == 1){
            return stack;
        }
        // 关系式
        int top = stack.pop();// stack = 1,2,3,4
        stack = reverse(stack);//stack = 4,3,2,1
        //把top放到栈底
        stack = pushFirst(stack, top);// stack=4,3,2,1 top = 5=>stack = 5,4,3,2,1
        return stack;
    }
    //把top放到栈底,比如stack=4,3,2,1 top = 5=>stack = 5,4,3,2,1
    public static Stack<Integer> pushFirst(Stack<Integer> stack, int top){
        if(stack.isEmpty()){
            stack.push(top);
            return stack;
        }
        //关系式
        int temp = stack.pop(); // temp = 1; stack = 4,3,2
        stack = pushFirst(stack, top);// stack = 4,3,2 top = 5=>stack=5,4,3,2
        stack.push(temp);// stack = 5,4,3,2,1
        return stack;

    }



    //-----------------------做法2-------------------
    // stack = 1,2,3,4,5=> stack = 5,4,3,2,1
    public static Stack<Integer> reverse1(Stack<Integer> stack){
        //结束条件
        if(stack.isEmpty() || stack.size() == 1){
            return stack;
        }
        // 关系式
        int last = getLast(stack);// last = 1, stack = 2,3,4,5
        stack = reverse1(stack);//stack = 5,4,3,2

        stack.push(last);// stack = 5,4,3,2,1
        return stack;
    }

    // stack = 1,2,3,4,5=>stack = 2,3,4,5 last = 1
    public static int getLast(Stack<Integer> stack){
        if(stack.size() == 1){
            return stack.pop();
        }

        //关系式
        int temp = stack.pop();// temp = 5, stack = 1,2,3,4
        int last = getLast(stack);// stack = 2,3,4
        stack.push(temp);// stack = 2,3,4,5
        return last;
    }

递归优化思路

案例：斐波那契数列

以往的代码

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

  //3.关系式
  return f(n-1) + f(n-2);//复杂度：2^n
}

有很多重复计算

优化思路：

1、考虑状态保存

//
int arr[] = new int[n+1];//初始值是0
int f(int n){
  if(n <= 2){
    return 1;
  }
  // 判断之前是否计算过
  if(arr[n] != 0){
    return arr[n];
  }

  //3.关系式
  int sum = f(n-1) + f(n-2);
    // 状态保存
  arr[n] = sum;
}

每一次递归都需要消耗栈空间，n很大时，容易出现栈溢出

f(n) = f(n-1) + f(n-2);

2、考虑自底向上

f(1) = 1

f(2) = 1;

f(3) = f(2) + f(1);

int f(int n){
  int dp[] = new int[n+1];

  dp[1] = 1;
  dp[2] = 1;
  for(int i = 3; i <= n; i++){
    dp[i] = dp[i-1] + dp[i-2];
  }

  return dp[n];
}