递归

[hushicai]

递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。

[hushicai]

递归的思想就是把问题分解成为规模更小的、具有与原问题有着相同解法的问题。

是不是这样的问题都能用递归来解决呢？答案是否定的。

一般来讲，能用递归来解决的问题必须满足两个条件：

• 可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式。
• 存在一种简单情境，可以使递归在简单情境下退出。

如果一个问题不满足以上两个条件，那么它就不能用递归来解决。

所以当我们考虑使用递归解决某个问题时，首先就需要考虑是否满足递归的两个条件。

参考漫谈递归：递归需要满足的两个条件

[hushicai]

递归三大要素

第一要素：明确函数功能

例如，定义了一个函数：

function factorial(n) {}

这个函数的功能就是计算 n 的阶乘。

第二要素：寻找结束条件

例如，当 n = 1 时，factorial(1) = 1；当n = 2时，factorial(2) = 2 * 1 = 2，那么结束条件就可以这么写：

function factorial(n) {
  if (n <= 2) {
    return n;
  }
}

第三要素：寻找等价关系

不断缩小参数范围（归纳），把问题蜕变成子问题的表达式（步进表达式）。

例如，factorial(n)等价为factorial(n) = n * factorial(n-1)：

function factorial(n) {
  if (n <= 2) {
    return n;
  }
  return n * factorial(n - 1);
}

参考为什么你学不会递归？告别递归，谈谈我的一些经验

[hushicai]

斐波那契数列

斐波那契数列：f(0) = 0, f(1) = 1, 对n > 1, f(n) = f(n-1) + f(n-2)。

从定义上看，显然这问题可以通过递归来解决的。

明确函数功能

function fibonacci(n) {}

寻找结束条件

function fibonacci(n) {
  if (n ===0) {
    return 0;
  } else if (n === 1) {
    return 1;
  }
}

寻找等价关系

function fibonacci(n) {
  if (n ===0) {
    return 0;
  } else if (n === 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

[hushicai]

回文串

“回文串”是一个正读和反读都一样的字符串，例如“level” 、“noon”。

首先我们考虑递归的两个条件：

第一：这个问题是否可以分解为形式相同但规模更小的问题？ 第二：如果存在这样一种分解，那么这种分解是否存在一种简单情境？

如果一个字符串是回文，那么在它的内部一定存在着更小的回文，比如level里面的eve也是回文，而且，一个回文的第一个字符和最后一个字符一定是相同的，所以我们可以得出：

先判断给定字符串的首尾字符是否相等，若相等，则判断去掉首尾字符后的字符串是否为回文，若不相等，则该字符串不是回文。

我们已经成功地把问题的规模缩小了，去掉首尾字符的字符串当然比原字符串小。

对于回文问题，我们容易发现，一个只有一个字符的字符串一定是回文，所以，只有一个字符是一个简单情境，但它不是唯一的简单情境，因为空字符串也是回文。

这样，我们就得到了回文问题的两个简单情境：字符数为1和字符数为0。

两个条件都满足了，因此我们可以使用递归来解决这个问题。

明确函数功能

// 是否是回文字符串
function isPalindrome(str) {}

寻找结束条件

function isPalindrome(str) {
  if (str.length === 0 || str.length === 1) {
    return true;
  }
}

寻找等价关系

function isPalindrome(str) {
  const len = str.length;
  const first = str[0];
  const last = str[str.length - 1];

  console.log('Length: ', len);
  console.log(first, '===========', last);

  if (len === 0 || len === 1) {
    return true;
  }

 // 如果首尾字符相同，则问题等价于求解子字符串的首尾字符是否相同
  if (first === last) {
    return isPalindrome(str.substring(1, str.length - 1));
  }
  return false;
}

参考漫谈递归：字符串回文现象的递归判断

[hushicai]

求和

function sum(n)
{
    if (n == 1) {
        return 1; // 这个就是递归的出口，化简为非递归状况处理
    } else {
        return sum(n - 1) + n; // 子问题须与原始问题
    }
}

示意图

参考面试中的递归算法，先收藏没准哪天就用上了！

[hushicai]

反转单链表

反转单链表，例如链表为1->2->3->4，反转后为 4->3->2->1。

首先考虑原问题能否拆成更小的子问题。

对于链表来说，就是缩小链表长度，如果我们先对 2->3->4递归，其反转结果如下：

  head —> 1
          |
          V
4 —> 3 —> 2

我们把 2->3->4 递归成 4->3->2，但节点1不变，仍然指向2。

接下来把节点2的next指向1，再把节点1的next指向null，结果如下：

             null <— 1
                     ^
                     |
newHead -> 4 —> 3 —> 2

然后对head为null或者header.next为null的节点，递归可以结束。

满足递归的两个条件，可以用递归来求解。

明确函数功能

function reverse(head) {}

寻找结束条件

function reverse(head) {
  if (head === null || head.next === null) {
    return head;
  }
}

寻找等价关系

function reverse(head) {
  if (head === null || head.next === null) {
    return head;
  }
  // head.next即缩小了链表长度
  let newHead = reverse(head.next);
  // 节点1
  let t1 = head;
  // 节点2
  let t2 = t1.next;
  t2.next = t1;
  t1.next = null;
  return newHead;
}

最终结果如下：

             null <— 1
                     ^
                     |
newHead -> 4 —> 3 —> 2

参考为什么你学不会递归？告别递归，谈谈我的一些经验