写递归的技巧

明白一个函数的作用并相信它能完成这个任务，千万不要试图跳进细节。千万不要跳进这个函数里面企图探究更多细节，否则就会陷入无穷的细节无法自拔，人脑能压几个栈啊。

  1. void traverse(TreeNode* root) {
  2.     if (root == null) return;
  3.     traverse(root->left);
  4.     traverse(root->right);
  5. }

这几行代码就足以扫荡任何一棵二叉树了。我想说的是，对于递归函数traverse(root)，我们只要相信：给它一个根节点root，它就能遍历这棵树，

递归的三大要素

第一要素：明确你这个函数想要干什么
第二要素：寻找递归结束条件
第三要素：找出函数的等价关系式

  1. // 算 n 的阶乘(假设n不为0)
  2. int f(int n){
  3.     if(n <= 2){
  4.         return n;
  5.     }
  6.     // 把 f(n) 的等价操作写进去
  7.     return f(n-1) * n;
  8. }
  11. //斐波那契数列
  12. int f(int n){
  13.     // 1.先写递归结束条件
  14.     if(n < 2){
  15.         return n;
  16.     }
  17.     // 2.接着写等价关系式
  18.     return f(n-1) + f(n - 2);
  19. }
  21. //小青蛙跳台阶
  22. int f(int n){
  23.     //f(0) = 0,f(1) = 1，等价于 n<=1时，f(n) = n。
  24.     if(n <= 1){
  25.         return 1;
  26.     }
  27.     ruturn f(n-1) + f(n-2);
  28. }

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

链接：https://leetcode-cn.com/problems/n-th-tribonacci-number

  1. const tribonacci = (n) => {
  2.     const res = [0, 1, 1];
  3.     const recursion = (n) => {
  4.         if (res[n] !== undefined) {
  5.             return res[n];
  6.         }
  7.         res[n] = recursion(n - 1) + recursion(n - 2) + recursion(n - 3);
  8.         return res[n];
  9.     };
  10.     return recursion(n);
  11. };