数据结构与算法分析(C++)(二)

1.1 递归简介(二)

查单词

通过这本书的介绍,我们将学会使用递归解决一些问题。例如,想象有一个大的字典。字典中的每个单词通过其他单词定义或解释。当我们查询一个单词时,我们并不一定能够理解该单词的解释,但是我们可以通过继续查询解释中不能理解的单词。就像这样,我们虽然不一定能够全部理解其中的部分,但是总能这样连续不断地继续查询,因为字典的内容是有限,最终可能出现两种情形:

  • 通过这样不断的查询,把解释该单词的不能理解的单词都查清楚,最后理解了该单词;
  • 在查询的时候,会发现解释该单词的不能理解的单词本身由是通过该单词解释的,那么我们就陷入了一个死循环;或者解释该单词的部分单词字典没有涵盖,那么我们就无法最终理解该单词。

由上分析,我们使用递归的方式理解单词的策略应该是(这里仅仅给出伪码):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void searchWords( string word )
{
if (understand(word)) // 理解该单词, understand为判断函数,理解则返回True,否则返回False
done; // 完成结束
else
{
vector<string> subWords = subWordsOfDefinition( word ); // 查询得到该单词的定义,subWords为该单词定义中出现的单词
int counts = subWords.size(); // 定义中出现单词的数量
int index = 0;
while (index < counts)
{
if (!understand(subWords[index])) // 如果不理解定义中出现的单词
searchWords(subWords[index]); // 继续查询
index ++;
}
}
}

通过这一过程,我们就能递归查询我们不认识的单词。如果这个字典定义完整,那我们就能最终理解这个单词,当然也有可能陷入到前面提到的第二种情形中。

打印输出数字

再看另一个问题,给出一个正整数,$n$,我们希望能够打印输出它。我们需要写一个处理函数printOut(n),你可能会想,直接一行命令cout << x << endl()不就行了吗,但是我们假设系统的I/O只允许打印输出单个数字。我们令这种打印输出指令为printDigit(),对于0~9范围内的整数输入,可以打印输出对应的数字,比如printDigit(4)会打印输出一个4;对于范围以外的输入,均认为非法输入。

递归就能很简洁地解决这一问题。例如,我们要打印输出76234,我们需要先打印输出7623然后打印4,而后者很容易通过取余实现:printDigit(n%10),但是前者跟打印输出76234没什么区别,还是同一问题。因此,我们可以通过递归的方式解决它:printOut(n/10)

这个例子告诉我们怎么使用递归去解决一般问题,但是在庆祝我们解决了打印输出数字问题之前,我们还是有必要进行确认程序不会进入类似查单词那样的死循环或者无解的状态中。前面一讲中已经说过,递归必须要有基准条件,打印输出数字的问题的基准条件很明显是: printDigit(n) 如果 n $ \in {0,1,2,3,4,5,6,7,8,9}$。所以对于$0 \sim 9$的基础数字,直接使用基准条件,而更大的数字又是通过这些小的基础数字构成,因此,可以认为在递归的过程中不会出现“死循环”等问题。通过这种不严格的分析,我们可以写出如下的打印输出数字的程序:

1
2
3
4
5
6
void printOut( int n )
{
if( n>= 10 )
printOut( n / 10 );
printDigit( n % 10 );
}

这段程序没有进行任何优化,我们其实可以通过避免使用趋于程序(比较耗时),因为取余的实际过程为: $ n\%10= n - \lfloor n/10 \rfloor * 10$($\lfloor x \rfloor$ 表示最大的不超过或者等于$x$的整数)。

当然,我们也可以使用严格的证明,例如使用数学归纳法证明我们提出的打印输出数字的算法时正确的,感兴趣可以尝试~

通过这些例子,我们可以得出递归的第三条准则:

  • Design rule: 假设所有的递归调用有效或能够运作。

这条准则非常重要,它意味着,在设计递归程序的时候,我们一般不必知道系统在使用递归过程中的记录管理的细节,当然更不必悉数去跟踪递归调用。一般而言,搞清楚递归调用过程中指令的真实时序简直难于上青天。

现在主要的问题就是,递归过程潜在的记录代价。虽然这些代价一般而言是可以接受的,加之递归过程可以简化算法设计,使代码更加简洁,但是还是应该牢记:递归不应当代替简单的循环(后面第3.6章会进行深入剖析)。

综上,当我们在写递归程序的时候,应该牢记四条准则:

  • Base case: 递归必须具有一些不需要通过递归就能得到结果的基准条件;
  • Making progress: 对于基准条件外的情形,递归总是能够朝着一个基准条件“推进”;
  • Design rule: 假设所有的递归调用有效或能够运作;
  • Compound interest rule: 绝不在几个递归调用中重复工作以解决同一个问题。

关于第四条准则,在这里解释一下,假设有一个函数$T(n) = \sum_{i=0}^{n-1}T(i) + n, \ T(0)=1 \ ^{[1]}$,如果不加思索,我们很容易写出如下递归程序:

1
2
3
4
5
6
7
8
9
10
11
int T(n)
{
if( n== 0 )
return 1;
int sum = 0;
for( int i=0; i<n-1; ++i )
{
sum += T(i);
}
return sum+n;
}

但是,当我们仔细分析这个函数的特点后,我们把递归过程画一个简图:

1
2
3
4
5
6
7
8
9
10
11
---------------------T(n)----------------------
/ / / / \
T(0) T(1) T(2) T(3) T(n-1)
| / \ / | \ ...
T(0) T(0) T(1) T(0) T(1) T(2) .
| | / \ .
T(0) T(0) T(0) T(1) ... .
|
T(0)
...

很明显,对于第$k$次递归,需要把其前面$0 \sim k-1$所有的递归过程重复一遍。计算$T(n)$的过程中,$T(n-1)$只被调用1次,$T(n-2)$倍调用2次,$T(n-3)$将被调用4次,于是我们可以得出对于中间的$T(n-k)$被调用次数为$2^{n-k-1}$次,于是这个递归调用过程的时间复杂度就为$O(2^n)$,也就是指数增长,难以想象当$n$的数值一旦较大的时候,程序将会耗费多少计算资源。

既然该递归过程中,造成了大量的重复计算,能不能避免呢?首先要做的就是对$T(n)$函数化简:

1
2
3
4
5
6
7
T(0) = 1
T(1) = 1 + 1
T(2) = 1 + (1 +1) + 2 = 2 + 1+2
T(3) = 1 + (1 + 1) + (2 + 1+2) + 3 = (4 +1+1+2+3)
T(4) = 1 + (1 + 1) + (2 + 1+2) + (4 + 1+1+2+3) + 4 = 8 +1+1+1+1+2+2+3+4
...
T(n) = 1*2^(n-1) + 1*2^(n-2) + 2*2^(n-3) + 3*2^(n-4) + ... + (n-1)*2^0 + n

这样就可以用一个简单的循环得到$T(n)$:

1
2
3
4
5
6
7
8
9
int T(n)
{
if( n== 0 )
return 1;
int sum = pow(2, n-1);
for( int i=1; i<n-1; ++i )
sum += i*pow(2, n-i-1);
return sum+n;
}

  1. Base cases. You must always have some base cases, which can be solved without recurision.
  2. Making progress. For the cases that are to be solved recurisively, the recurisive call must always be to a case that makes progress toward a base case.
  3. Desgin rule. Assume that all the recurisive calls work.
  4. Compound interest rule. Never duplicate work by solving the same instance of a problem in separate recursive calls.

参考资料