编程马拉松 Day02 递归

今天是第二天，继续我们的征程。

题目

编写代码，把字符串中的每个空格替换为%20。例如，输入"hello world."，则输出"hello%20world."。
编写代码，给定系数n，求1+2+3+…+n的总和，即∑运算符
编写代码，观察如下数列，给定系数n，求数列中的第n个数字(tips: 斐波那契数列)。 1 1 2 3 5 8 13 21 34 55 89 ...

字符替换

本题是将空格等特殊字符变为转义字符的函数，常用于URL编码中，用来避免URL中可能存在的字符歧义。

 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
/**
 * 判断当前字符是否为普通字符
 */
public static boolean isPlainChar(char c) {
    return (c >= '0' && c <= '9') ||
            (c >= 'a' && c <= 'z') ||
            (c >= 'A' && c <= 'Z') ||
            c == '!' || c == '$' || c == '-' || c == '.' || c == '+' ||
            c == '*' || c == '\'' || c == '(' || c == ')' || c == ',';
}
public static char[] encodeMap(char c) {
    //构造特殊字符映射表
    String[] map = new String[256];
    map[' '] = "%20";
    map['/'] = "%2F";
    map['?'] = "%3F";
    map['%'] = "%25";
    map['#'] = "%23";
    map['&'] = "%26";
    map['='] = "%3D";
    return map[c].toCharArray();
}
public static char[] urlEncode(char source[]) {
    int needLength = 0;
    for (int i = 0; i < source.length; i++) {
        char c = source[i];
        if (isPlainChar(c)) {
            needLength++;
        } else {
            needLength += encodeMap(c).length;
        }
    }
    char result[] = new char[needLength];
    int resultIndex = 0;
    for (int i = 0; i < source.length; i++) {
        char c = source[i];
        if (isPlainChar(c)) {
            result[resultIndex] = c;
            resultIndex++;
        } else {
            char encodeStr[] = encodeMap(c);
            System.arraycopy(encodeStr, 0, result, resultIndex, encodeStr.length);
            resultIndex += encodeStr.length;
        }
    }

    return result;
}
//===========
//测试代码
public static void main(String args[]) {
    char[] source = "hello world.".toCharArray();
    System.out.println(urlEncode(source));
}

累加和 `∑`

正向循环解题

要求n个数字的和，则需求出 f(1)+f(2)+...+f(n-1)+f(n)。本题中等差数列的公差为1，则f(1) == 1 ,f(2) == 2...

1
2
3
4
5
6
7
public static int sigmaAdd(int n){
    int sum = 0;
    for (int i = 1;i<=n;i++){
        sum+=i;
    }
    return sum;
}

逆向递归求解

通过观察数列，不难看出数列的如下性质: f(n) = f(n-1) + 1 我们可以将∑n的问题转化为 f(n) + f(n-1) +...+ f(2) + f(1)，则可以使用递归来求解

1
2
3
4
5
6
7
public static int sigmaAdd2(int n) {
    if (n > 1) {
        return n + sigmaAdd(--n);
    } else {
        return 1;
    }
}

递归在算法中的应用非常广泛，许多看似复杂的多重循环问题，都可以通过递归加中止条件写出较为简洁的代码

斐波那契数列

递归算法

先来看斐波那契数列的性质：

当n=0时，f(n) = 0
当0=1时，f(n) = 1
当n>1时，f(n) = f(n-2) + f(n-1)

根据其性质，很容易通过递归写出其代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public static int fibonacci(int n) {
    if (n <= 0) {
        return 0;
    } else if (n < 2) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
//===========
//测试代码
public static void main(String args[]){
    System.out.println(fibonacci(20));
}

递归的代码虽然简洁，但简洁不代表简单。以求得f(10)为例，需要先求得f(9)和f(8)。同样，想求得f(9)，需要先求得f(8)和f(7)…我们可以用树形结构来表示这种依赖关系，如下图所示。基于递归求斐波那契数列的第10项的调用过程不难发现，树中有很多结点是重复的，而且重复的结点数会随着n的增大而急剧增加，这意味着计算量会随着n的增大而急剧增大。你可以试下用递归方式求斐波那契数列的第50项试试，感受一下这样的递归会有多慢。

非递归算法

递归方法之所以慢，是因为重复计算太多，只需想办法避免重复计算，即可加快其速度。比如我们可以把之前计算过的结果保存下来，便于下次计算。

比如先根据f(0)和f(1)得到f(2)，再根据f(1)和f(2)得到f(3)，每次结果均保留，依次类推即可得到第n项的值，其时间复杂度为O(n)。实现代码如下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public static long fibonacci2(int n) {
    int fib[] = new int[]{0, 1};
    if (n < 2) return fib[n];
    long fib1 = 1;
    long fib2 = 0;
    long result = 0;
    for (int i = 2; i <= n; i++) {
        result = fib1 + fib2;
        fib2 = fib1;
        fib1 = result;
    }
    return result;
}

时间对比

基准	递归方式	非递归方式
fib(20)耗时	0ms	0ms
fib(30)耗时	4ms	0ms
fib(40)耗时	383ms	0ms
fib(50)耗时	44269ms	0ms

通过表格可以看到，在时间方面非递归方式有着显著的优势。除了时间的开销，递归过程中还会创建多个函数栈，每个函数栈都有自己的参数，返回值等信息，因此递归也会给栈的内存空间带来一定的压力。如StackOverflow调用栈溢出异常就是由于栈空间不足引起的。

从思路上来讲，递归采用的是自顶向下的方式，将一个个较大的问题分解为若干个较小的问题（如 f(10) = f(9) + f(8)），但小的问题可能会有多次重复计算。我们可以反其道而行之，采用自底向上的方式，先从小问题开始处理，记录小问题的结果，然后根据小问题的结果来解答较大的问题，以此类推，得到特定问题的解。

扩展

通过今天的练习，我们分析了递归的一些优缺点。在编写代码时，要了解递归潜在的问题，在一些注重性能的场合，尽量采用循环来代替递归，从而提高程序的运行效率。此外在面试中，编程题通常不会太直白的表现出来，面试官往往会将问题包装一下，以此来考察我们的分析与建模能力，如下边几个问题。

上台阶问题，一共有n个台阶，每次可以上1阶或2阶，那么上到第n阶有几种方法。
小马过河问题，河中有n块石头，小马每次能跳过1块或2块石头，那么跳过n块石头有几种方法。
如下图所示，用左边的2*1的小矩形横着或者竖着去覆盖右边2*8的大矩形，在不发生重叠的情况下，总共有多少种方法？

扩展题答案

前两个问题基本一致，我们先来分析问题。假设有n个台阶，则第一步有两种方法

若上1个台阶，则剩下n-1个台阶
若上2个台阶，则剩下n-2个台阶

以此类推，不难得出 f(n) = f(n-1)+ f(n-2) 这个式子，是不是很熟悉呢？对的，前两个问题仍是斐波那契数列相关的应用题，有公式后不难得出其答案。

接下来看第三个问题。我们先把2*8的覆盖方法记为f(8)。用第一个2*1的小矩形去覆盖大举证的最左边边时有两种选择：

竖着放，则右边还剩2*7的区域，记为f(7)
横着放，则左下方也只能横着放一个2*1的小举证，右边还剩下 2*6的区域，记为f(6)

因此f(8) = f(7) + f(6)，此时可以看出，这仍然是斐波那契数列。

参考书目《剑指offer》2.4.1

题目#

字符替换#

累加和 ∑#

正向循环解题#

逆向递归求解#

斐波那契数列#

递归算法#

非递归算法#

扩展#

扩展题答案#

题目