递归思维

介绍

将大问题转化为小问题，通过递归依次解决各个小问题。

首先说明一个问题，简单阐述一下递归，分治算法，动态规划，贪心算法这几个东西的区别和联系，心里有个印象就好。 递归是一种编程技巧，一种解决问题的思维方式；分治算法和动态规划很大程度上是递归思想基础上的（虽然动态规划的最终版本大都不是递归了，但解题思想还是离不开递归），解决更具体问题的两类算法思想；贪心算法是动态规划算法的一个子集，可以更高效解决一部分更特殊的问题。 分治算法将在这节讲解，以最经典的归并排序为例，它把待排序数组不断二分为规模更小的子问题处理，这就是 “分而治之” 这个词的由来。显然，排序问题分解出的子问题是不重复的，如果有的问题分解后的子问题有重复的（重叠子问题性质），那么就交给动态规划算法去解决！ by——labuladong: https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/di-gui-xiang-jie

学习资料

递归详解

练习

• reverse-string
• swap-nodes-in-pairs
• unique-binary-search-trees-ii
• fibonacci-number

示例

reverse-string

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

var reverseString = function(s) {
    var reverse = function(str,star,end) {
        console.log(star,end);
        if(star > end) return str;
        reverse(str, star+1, end-1);
        [str[end], str[star]] = [str[star], str[end]];
    };
    return reverse(s,0, s.length -1)
};

swap-nodes-in-pairs

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

var swapPairs = function(head) {
    if(head == null || head.next == null) return head;
    let t1 = head;
    let t2 = head.next;
    t1.next = swapPairs(t2.next);
    t2.next = t1;
    return t2;
};

unique-binary-search-trees-ii

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

var generateTrees = function (n) {
  function buildTree(start, end) {
    let ans = [];
    if (start > end) return [null];
    for (let i = start; i <= end; i++) {
      let leftNodes = buildTree(start, i - 1);
      let rightNodes = buildTree(i + 1, end);
      for (const leftNode of leftNodes) {
        for (const rightNode of rightNodes) {
          let cur = new TreeNode(i);
          cur.left = leftNode;
          cur.right = rightNode;
          ans.push(cur);
        }
      }
    }
    return ans;
  }
  if (n === 0) return [];
  return buildTree(1, n);
}

path-sum-iii

var pathSum = function(root: TreeNode | null, sum: number): number {
    if(root == null ) return 0;
    var countPath = function(root: TreeNode | null, sum: number): number {
        if(root == null ) return 0;
        sum = sum - root.val;
        let result:number = sum == 0 ? 1 : 0;
        return result + countPath(root.left, sum) +  countPath(root.right, sum);
    }
    return countPath(root,sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
};

递归+备忘录

fibonacci-number

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。

var fib = function(N) {
    let m = {};
    function dfs(n) {
        if(n < 2) {
            return n
        }
        let result  = 0;
        if(m[n]) {
            return m[n];
        }
        result = dfs(n-2) + dfs(n-1);
        m[n] = result;
        return result;
    }
    return dfs(N);
};