-
递归和迭代术语的定义是什么？一个函数可以同时采用这两种方法吗？
- 递归：将一个大的问题分解成比较小的、有着相同形式的问题。
- 迭代：重复执行一项任务。
-
递归和逐步求精法的根本区别是什么？
- 递归所分解出的问题具有相同的形式，而逐步求精分解则不一定具备这个特性。
-
再CollectContributions函数的伪码中，为什么使用 if (n<=100)替代对n是否等于100的核算，这种核算为什么重要？
- 因为筹集的款项并不只是100美元的倍数，分解下来后，可能会出现每个人筹集款项少于100
-
什么是标准的递归范式？
if (test for simple case) { compute a simple solution without using recursion; } else { Break the problem down into subproblems of the same form; Solve each of the subproblems by calling this function recursively; Reassemble the solutions to the subproblems into a solution for the whole. }
-
要让递归成为一个解法，问题所必须具备的两个特征是什么？
- 必须能够鉴别出一个简单情景，且该情景的答案是容易确定的。
- 必须能够确定一个递归的分解方式，能够将问题的复杂实例分解为更小的、具有相同形式的问题。
-
为什么说分而治之是对递归技术最恰当的描述？
- 分治就是将大问题被逐步分解为多个小问题，解决小问题就解决了大问题；递归的解法也是将大问题分解成模式相同的小问题，在最简单的情况下解决。
-
对递归跳跃的信任是什么意思？为什么这个概念对程序员来说是很重要的？
- 抛开底层细节，在一个层次上思考，假设其它层次都已经做正确了；这个信任是递归调用能成立的基础，否则程序就会陷入无尽的细节之中。
-
在4.2.2小节“追踪递归过程”中，对调用Fact(4)时程序如何运行进行了大篇幅的分析。把这种分析作为一个模型，追踪Fib(4)的执行过程，画出进程中的每一个栈帧的略图。
- 略。
-
引入成对的兔子在生下3胎后停止繁殖这个规律，修改斐波那契的兔子问题，这种假设时如何改变递归关系的？在简单情景中，您需要做的改变是什么？
- 递推数列变为：1 1 2 3 5 7 11 16 24 35 52 76 112...
- 根据每对兔子第二个月发育成熟，第三个月生第一对，最多生3对的关系推测出数列改编为 a(n)= a(n-1) + a(n-2) - a(n-5), 当n<=5时最后一项为0
- 所以我们需要改变递推式，并且根据情况改变最后一项的值。
-
在图4-1给出的递归实现中，当计算Fib(n)时调用了多少次Fib(1)？
- 5次
-
如果从函数AdditiveSequence中将if(n==1)删除，程序会发生什么事情？该函数还能正常工作吗？为什么？
static int AdditiveSequence(int n, int t0, int t1) { if (n == 0) { return t0; } else { return AdditiveSequence(n - 1, t1, t0 + t1); } }
- 程序依旧可以正确运行，只是在微观层面，此函数会被多调用一次。因为实际上即使不能在n==1的情况下返回，这时的t0 + t1会作为下一次的t0值调用，最后n == 0时返回t0即可。
-
什么是包装器函数？为什么它们在写递归程序时用处很大？
- 包装器函数就是一个直接返回其它函数调用的函数，它可能会额外传递一些参数，在最上层调用时，无需关心额外参数，帮助我们减少复杂度，更直观地理解问题。
- 被包装的函数通常可以解决更加普遍的问题。
-
在图4-3的IsPalindrome视线中，为什么对空字符串的校验和对单字符的校验同样重要？如果不对单字符情景进行校验，而仅仅对长度为0的情形进行校验，将会发生什么？这个函数还能够正确运行吗？
- 因为存在双数字符的回文，每次调用减少2的字符长度，存在到最后为空串的校验；
- 如果不检测单字符的情况，会出现调用为负数的情况，这不符合实际情况，程序将发生错误。
-
解释图4-4中给出的函数IsPalindrome实现中函数调用CheckPalindrome(str+1, len-2)的作用。
- 使用指针忽略已经处理的字符串的第一个字符，并缩小问题的规模。
-
什么是交互递归？
- 交互递归是更加深层次的递归调用，f调用g，g再调用f。
-
如果按下面的方式定义了IsEven和IsOdd将会发生什么？
bool IsEven(unsigned n) { return (!IsOdd(n)); } bool IsOdd(unsigned n) { return (!IsEven(n)); }
- 递归永无终止，栈溢出。
-
下面对IsEven和IsOdd的定义也是不正确的，请给出一个演示和这个实现是如何是如何失败的示例。它属于什么常见错误？
bool IsEven(unsigned n) { if (n == 0) { return TRUE; } else { return IsOdd(n - 1); } } bool IsOdd(unsigned n) { if (n == 1) { return TRUE; } else { return IsEven(n - 1); } }
- 例如，调用 IsOdd(4)，程序将永无终止地运行，直到栈溢出。运行到n == 1时，程序在IsEven不具备退出条件。这个问题属于没有正确解决简单情形。