第5章递归.pdf

本章内容主要介绍了递归算法在不同场景下的应用和设计。通过递归算法解决特定问题，可以有效地简化问题的复杂性，并通过不断将问题分解为更小的子问题来达到解决目的。在递归函数设计中，需要注意递归出口（也称为基准情形）的设置，以防止无限递归的发生。 1. 递归函数输出结果分析 递归函数`fun`在调用`fun(5)`时，其输出结果可通过分析递归函数调用过程来确定。递归函数先进行递推（递归调用），直到达到递归出口（n==1），然后开始求值并逐层返回。因此，输出顺序是先递推输出`b:5`到`b:1`，然后回溯输出`c:2`到`c:5`，最后输出`a:1`。 2. 计算数组元素平均值 递归算法设计用于计算整数数组`A[0..n-1]`的平均值。通过递归函数`avg`，逐步计算出前`i`个元素的平均值，并最终计算出整个数组的平均值。算法的核心是`avg(A,i)=(avg(A,i-1)*i+A[i])/(i+1)`，当`i=0`时，直接返回数组的第一个元素作为平均值。 3. 计算正整数n的位数 递归算法用于求解正整数`n`的位数。函数`fun`通过判断`n`是否小于`10`来确定是否为一位数，否则通过`fun(n/10)+1`来递归求解，从而得到`n`的位数。 4. 楼梯走法数量计算 这是一个经典的递归问题，即计算走上n阶楼梯的不同走法数。递归关系为`f(n)=f(n-1)+f(n-2)`，其中`f(1)=1`（只有一步），`f(2)=2`（一步走一阶或两步走两阶）。通过递归函数`fun`可以计算出任意阶数楼梯的走法。 5. 顺序串的逆串 递归算法用于计算顺序串`s`的逆串。递归模型为`f(s)=s`如果`s`为空串，否则`f(s)=Concat(f(SubStr(s, 2, StrLength(s)-1)), SubStr(s, 1, 1))`，即将`s`的子串`s2s3...sn`的逆串与`s`的第一个字符所构成的串连接起来。 6. 单链表结点数量 递归算法用于计算不带表头结点的单链表`L`的结点数量。通过递归函数`count`，当`L`为空时返回`0`，否则返回`count(L->next)+1`。 7. 单链表输出结点值 设计了两个递归算法`traverse`和`traverseR`，分别用于正向和反向输出单链表的所有结点值。正向输出在递归调用返回前打印当前结点的数据，而反向输出在递归调用返回后打印当前结点的数据。 8. 单链表删除结点 设计了两个递归算法`del`和`delall`用于删除单链表中值为`x`的结点。`del`函数删除找到的第一个值为`x`的结点，而`delall`函数删除所有值为`x`的结点。删除结点时，需要注意内存的释放，避免内存泄漏。 递归算法的应用广泛，它能够以一种简洁且优雅的方式表达问题的解决方案，尤其适合解决可递归定义的问题。在使用递归时，我们需要对递归深度有充分的估计，避免栈溢出等问题。此外，递归算法在某些情况下可能效率不高，特别是当递归深度较大时，因此在实际应用中可能需要考虑转换为迭代算法或者使用动态规划等方法来优化性能。