课上练习

• 阿克曼函数：L3081

测试数据：

知识总结

基本概念

递推（迭代）：

递推是一种利用循环结构来重复计算的方法。在递推中，问题的每个后继状态都是从前一个状态直接推导出来的，整个过程中不涉及多个分支的自我调用。

递归：

递归是一种函数自我调用的过程，用来解决分而治之的问题。递归函数通过调用自身的同名函数来达到重复计算的目的，并且每次调用时问题规模都有所减小，直至达到边界条件。

实现方式

递推：

1.使用循环结构（如 for 或 while 循环）。

2.显式地通过迭代来更新状态。

3.通常更直观，因为它直接反映了从初始状态到结果状态的计算过程。

递归：

1.函数中调用自身。

2.需要适当的边界条件来停止递归。

3.可以更简洁地表达，特别是在解决复杂问题时，代码更为简练。

性能和资源消耗

递推：

1.空间效率高，因为不需要额外的函数调用堆栈。

2.在执行速度上通常比递归快，因为没有函数调用和返回的开销。

递归：

1.空间效率较低，每一次函数调用都会消耗堆栈空间，且在调用深度很大时可能导致堆栈溢出。

2.执行速度可能不如递推快，特别是当递归调用非常频繁时。

适用场景

递推：

适合于那些可以直接从一个状态推到下一个状态的问题，如斐波那契数列的计算、简单的数列求和等。

递归：

适合于解决复杂的问题，如快速排序、归并排序、搜索算法等，这些问题可以自然地分解成更小的子问题。

递推与递归的对比

递推

递归

计算方式

使用循环

使用函数自己调用自己

使用问题

有递推公式的问题

把问题规模逐渐缩小的问题

解决顺序

从前到后

从大到小

常见题型

数列计算 贪心问题 动态规划

数列计算 不知道具体次数的枚举 分治法应用 搜索算法

难点

寻找递推公式

子问题拆分

️课后作业

☝️总结作业

总结作业非常重要，请务必认真完成✔️

• 总结使用递推的好处。
• 总结使用递归的好处。

✌️编程作业

考试只有一次提交机会，请务必本地检查正确后再提交❇️

• 汉诺塔的移动次数：L3082