Skip to content

Latest commit

 

History

History
252 lines (138 loc) · 8.45 KB

recursiveAlgorithm.md

File metadata and controls

252 lines (138 loc) · 8.45 KB

递归

引用自：LeetCode 递归Ⅰ

简介

递归是计算机科学中的一个重要概念。它是许多其他算法和数据结构的基础。然而，对于许多初学者来说，掌握它可能是一件非常棘手的事情。

在开始本章探索前，我们强烈建议您预先完成二叉树和栈和队列这两章

递归原理

递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用

你可能想知道如何实现调用自身的函数。诀窍在于，每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到到子问题无需进一步递归就可以解决的地步。

为了确保递归函数不会导致无限循环，它应具有以下属性：

  1. 一个简单的基本案例（basic case）（或一些案例） —— 能够不使用递归来产生答案的终止方案。
  2. 一组规则，也称作递推关系（recurrence relation），可将所有其他情况拆分到基本案例。

注意，函数可能会有多个位置进行自我调用。

1. 以相反顺序打印字符串

让我们从一个简单的编程问题开始：

以相反的顺序打印字符串。

你可以使用迭代的办法轻而易举地解决这个问题，即从字符串的最后一个字符开始遍历字符串。但是如何递归地解决它呢？

首先，我们可以将所需的函数定义为 printReverse(str[0...n-1])，其中 str[0] 表示字符串中的第一个字符。然后我们可以分两步完成给定的任务：

  1. printReverse(str[1...n-1])：以相反的顺序打印子字符串 str[1...n-1] 。
  2. print(str[0])：打印字符串中的第一个字符。

请注意，我们在第一步中调用函数本身，根据定义，它使函数递归。

下面给出了代码片段：

private static void printReverse(char [] str) {
  helper(0, str);
}

private static void helper(int index, char [] str) {
  if (str == null || index >= str.length) {
    return;
  }
  helper(index + 1, str);
  System.out.print(str[index]);
}

2. 反转字符串

题目描述

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

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

题目分析

仔细观察问题所带来的约束，如果我们把它放到递归的环境中，我们可以把它解释为在两个连续的递归调用之间没有额外的空间消耗，也就是说，我们应该把问题划分为独立的子问题。

因此，关于如何划分问题的一个想法是将每个步骤中的输入字符串减少为两个组件：1). 前导字符和末尾字符。 2). 没有前导字符和末尾字符的其余子字符串。 然后我们可以独立地解决这两个部分。

根据上述思想，我们可以提出如下算法:

  1. 从输入字符串中获取前导字符和尾随字符，即 str[0] and str[n-1].
  2. 就地交换前导字符和末尾字符
  3. 递归调用函数来反转剩余的字符串，也就是 reverseString(str[1...n-2]).

请注意，实际上可以交换步骤*（2）和（3）*的顺序，因为它们是独立的任务。 但是，最好是按照这个顺序保存它们，因为这样我们就可以使用称为尾递归的优化。 我们将在后面的章节中进一步阐述尾递归。

给定输入字符串 ["h", "e", "l", "l", "o"]，我们将会演示如何分解并解决它：

img

可以看出，每次递归调用只需要常量级的内存，以便交换前导和末尾字符。结果显而易见，它满足了问题的约束。

代码实现

Go

func reverseString(s []byte)  {
    helper(s, 0, len(s)-1)
}

func helper(s []byte, l, r int) {
    if l >= r {
        return
    }
    s[l], s[r] = s[r], s[l]
    helper(s, l+1, r-1)
}

3. 两两交换链表中的结点

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

代码实现

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    // 1->2->3->4
    newHead := head.Next // 2
    head.Next = head.Next.Next // 1->3
    newHead.Next = head // 2-> 1
    head.Next = swapPairs(head.Next) // 1->4
    
    return newHead
}

递推关系

在实现递归函数之前，有两件重要的事情需要弄清楚:

  • 递推关系： 一个问题的结果与其子问题的结果之间的关系。
  • 基本情况: 不需要进一步的递归调用就可以直接计算答案的情况。 有时，基本案例也被称为 bottom cases，因为它们往往是问题被减少到最小规模的情况，也就是如果我们认为将问题划分为子问题是一种自上而下的方式的最下层。

一旦我们计算出以上两个元素，再想要实现一个递归函数，就只需要根据递推关系调用函数本身，直到其抵达基本情况。

为了解释以上几点，让我们来看一个经典的问题，帕斯卡三角（Pascal's Triangle）:

帕斯卡三角形是排列成三角形的一系列数字。 在帕斯卡三角形中，每一行的最左边和最右边的数字总是 1。 对于其余的每个数字都是前一行中直接位于它上面的两个数字之和。

下面的插图给出了一个 5 行的帕斯卡三角：

Pascal_Triangle

根据上面的定义，我们生成一个具有确定行数的帕斯卡三角形。

递推关系

让我们从帕斯卡三角形内的递推关系开始。

首先，我们定义一个函数 f(i, j)，它将会返回帕斯卡三角形第 i 行、第 j 列的数字。

我们可以用下面的公式来表示这一递推关系：

f(i, j) = f(i - 1, j - 1) + f(i - 1, j)

基本情况

可以看到，每行的最左边和最右边的数字是基本情况

因此，我们可以将基本情况定义如下:

f(i,j) = 1 where j = 1 or j = i

演示

正如我们所看到的，一旦我们定义了 ，递归函数的实现变得更加直观，特别是在我们用数学公式表示出这两个元素之后。

下面给出一个例子，展示我们如何用这个公式递归地计算 f(5, 3), 也就是 帕斯卡三角形第 5 行中的第 3 个数。

Pascal_Triangle

我们可以将f(5, 3)分解为f(5, 3) = f(4, 2) + f(4, 3)，然后递归地调用f(4, 2)和f(4, 3)：

  • 对于调用的f(4, 2)，我们可以进一步展开它，直到到达基本情况，正如下面所描述的：

    f(4, 2) = f(3, 1) + f(3, 2) = f(3, 1) + (f(2, 1) + f(2, 2)) = 1 + (1 + 1) = 3

  • 对于调用f(4, 3)`，类似地，我们可以将其分解为：

    f(4, 3) = f(3, 2) + f(3, 3) = (f(2, 1) + f(2, 2)) + f(3, 3) = (1 + 1) + 1 = 3

  • 最后，我们结合上述子问题的结果：

    f(5, 3) = f(4, 2) + f(4, 3) = 3 + 3 = 6

下一步

在上面的例子中，您可能已经注意到递归解决方案可能会导致一些重复的计算，例如，我们重复计算相同的中间数以获得最后一行中的数字。 举例说明，为了得到f(5, 3)的结果，我们在f(4, 2)和f(4, 3)的调用中计算了f(3, 2)两次。

我们将在探索卡的下一章中讨论如何避免这些重复计算（duplicate calculations）。

在本文之后，你将会找到与帕斯卡三角相关的问题作为练习。