发表于   |     |   阅读次数

什么是尾递归

尾递归是指递归调用作为函数执行的最后一条语句，这样的情况下递归调用发生时，当前的栈帧就不需要了。如果语言有对尾递归做这样的优化，那么不论尾递归调用多少层，都不会有栈溢出的风险。特别注意的是，类似于下面这样的代码不是尾递归的，因为它执行的最后一条语句是 h + sum_result 而不是 sum(t) ，换句话说，这里调用 sum 时，栈帧还不能抛弃，因为栈帧中还需要保存 h 。
更详细的介绍请看： https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8

1
2
3
4
def sum(list: List[Int]): Int = list match {
  case Nil => 0;
  case h::t => h + sum(t)
}

非尾递归的实现

1
2
3
4
def foldRight2[E, B](l: List[E], b: B)(op: (E, B) => B): B = l match {
  case Nil => b
  case h::t => op(h, foldRight(t, b)(op))
}

以上代码以一种最容易想到的方法实现了 foldRight， 但是很遗憾，它不是尾递归。::方法是常量时间完成，不涉及递归，后面不再解释。递归调用 foldRight 返回后还需要使用 h 和递归结果作为参数调用 op，栈帧中还需要保存 h 和 op，所以以上实现不是尾递归的。

尾递归的实现

虽然直接实现 foldRight 的尾递归版本有困难，但是 foldLeft 却很容易用尾递归实现。那我们实现一个尾递归的foldLeft，然后翻转 list 调用 foldLeft ，以此来实现 foldRight ，这样可行吗？下面试试看。

尾递归的 foldLeft

1
2
3
4
def foldLeft[E, B](l: List[E], b: B)(op: (B, E) => B): B = l match {
  case Nil => b
  case h::t => foldLeft(t, op(b, h))(op)
}

以上实现，最后执行的代码就是对foldLeft的递归调用，栈帧中需要保存任何信息，显然是尾递归的。

使用 foldLeft 实现 foldRight

1
2
3
4
def foldRight[E, B](l: List[E], b: B)(op: (E, B) => B): B = l match {
case Nil => b
case h::t => foldLeft(reverse(l), b)((b, e) => op(e, b))
}

这样就完了吗？当然没有，上面的实现使用了reverse函数，得尾递归实现reverse才行

尾递归实现reverse

这里就不卖关子了，直接使用 foldLeft 来实现 reverse 就可以了。

1
2
3
4
def reverse[E](l: List[E]): List[E] = l match {
  case Nil => Nil
  case h::t => l.foldLeft(Nil:List[E])((b, e) => e::b)
}

结果检验

上面有了 foldRight2 和 foldRight 两个实现。我们用一个长 list 来分别调用两个函数看看是否栈溢出。

1
2
3
4
5
6
7
object App {
  def main(args: Array[String]): Unit = {
    def bigList = 1.to(10000).toList
    println(foldRight2(bigList, 0)((e, b) => e + b))
    //println(foldRight(bigList, 0)((e, b) => e + b))
  }
}

上面使用了一个长度为10000的 list，计算所有元素的和。
使用 foldRight2 时发生了栈溢出，根据jvm启动参数的不同，发生栈溢出的临界值是不一样的。

Alt text

使用 foldRight 时正确输出了结果

Alt text

说明这里的尾递归实现是正确的，并且Scala的做出了正确的优化。

发表于   |     |   阅读次数

题目

给定一个 M × N 的矩阵，找出其中最长的递增序列的长度
递增序列的方向可以是当前元素的上下左右，但不能是对角线，也不可以跨越边界

Example1

1
2
3
4
5
nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

返回值是4，最长的递增序列是：1，2，6，9

Example2

1
2
3
4
5
nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

返回值是4，最长的递增序列是：2，4，5，6 或者 3，4，5，6

题目来源： Longest Increasing Path in a Matrix

思路

方法很直观，依次计算每一个元素的最长递增路径长（下面简称LI），然后选取最大的值作为最终结果。

然后要考虑的是，如何计算每一个元素的LI。很容易想到，每个元素有2-4个相邻元素，要计算当前元素的LI，
先要找出值比当前元素大的相邻元素，并计算每个相邻元素的LI，然后找出最大的相邻元素LI，加上1就是当前元素的LI。如果所有相邻元素的值都不比当前元素大，则当前元素的LI为0。

上述就是一个递归过程，递归结束点就是值大于等于所有相邻元素的元素。

按照以上思路实现应该就可以输出正确答案了，但是未必能被Accepted（猜的，我没试过）。因为上述算法虽然能输出正确结果，但是每个元素都可能计算多次LI。所以，我们还应该对每个元素的LI进行缓存，确保每个元素只计算一次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        #参数检查
        if matrix is None:
            return 0
        matrixSize = len(matrix)
        if len(matrix) == 0:
            return 0
        #初始化存放increasingPaths的数组
        increasingPaths = [[0 for j in range(len(matrix[i]))] for i in range(matrixSize)]
        #对每一个元素计算increasingPath
        for i in range(0, matrixSize):
            for j in range(0, len(matrix[i])):
                self.calculateIncreasingPath(matrix, i, j, increasingPaths)
        #选出最大的increasingPath并返回
        return max([max(x) for x in increasingPaths])
    def calculateIncreasingPath(self, matrix, i, j, increasingPaths):
        #如果已经计算过，则直接返回缓存的值
        if increasingPaths[i][j] != 0:
            return increasingPaths[i][j]
        nodeValue = matrix[i][j]
        #计算上方相邻元素
        upPathLen = 0
        if i > 0 and matrix[i - 1][j] > nodeValue:
            upPathLen = self.calculateIncreasingPath(matrix, i - 1, j, increasingPaths)
        #计算左边相邻元素
        leftPathLen = 0
        if j > 0 and matrix[i][j - 1] > nodeValue:
            leftPathLen = self.calculateIncreasingPath(matrix, i, j - 1, increasingPaths)
        #计算下面相邻元素
        downPathLen = 0
        if i < len(matrix) - 1 and matrix[i + 1][j] > nodeValue:
            downPathLen = self.calculateIncreasingPath(matrix, i + 1, j, increasingPaths)
        #计算右边相邻元素
        rightPathLen = 0
        if j < len(matrix[i]) -1 and matrix[i][j + 1] > nodeValue:
            rightPathLen = self.calculateIncreasingPath(matrix, i, j + 1, increasingPaths)
        #找出相邻元素中最大的increasingPath，加上1作为当前元素的increasingPath
        increasingPath = max([upPathLen, leftPathLen, downPathLen, rightPathLen]) + 1
        #缓存计算结果
        increasingPaths[i][j] = increasingPath
        return increasingPath

发表于   |   分类于   |     |   阅读次数

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment