分治递归

递归与分治算法心得
递归与分治算法都是常用的算法思想，可以很好地解决复杂问题。

递归算法是通过将问题分解为相同或相似的子问题来解决整个问题，然后再逐步合并回原问题的过程。

递归算法通常需要明确边界条件，以确保递归能够正确地停止。

分治算法是将问题分解成若干个相同或相似的子问题，递归地解决这些子问题，然后合并这些子问题的解来解决原始问题。

通常，分治算法可以高效地解决问题，但需要注意分解问题的方式和合并子问题的解的过程。

在实际应用中，递归和分治算法可以相互结合，以解决更加复杂的问题。

例如，可以使用分治算法来将问题分解成多个子问题，然后使用递归算法来解决这些子问题。

此外，还可以在递归算法中使用分治算法来对子问题进行分解和合并。

总而言之，递归与分治算法都是非常有用的算法思想，可以在许多领域中得到应用。

但是，在实际使用时，需要仔细考虑问题的性质和算法的复杂度，以确保算法的正确性和效率。

- 1 -。

递归和分治法摘要：1.递归和分治法的定义2.递归和分治法的区别3.递归和分治法的应用实例4.递归和分治法的优缺点正文：递归和分治法是计算机科学中常用的两种算法设计技巧。

它们在解决问题时都采用了将问题分解成更小子问题的思路，但在具体实现上却有所不同。

下面，我们来详细了解一下递归和分治法。

1.递归和分治法的定义递归法是指在算法中调用自身来解决问题的方法。

递归函数在执行过程中，会将原问题分解成规模更小的相似子问题，然后通过调用自身的方式，解决这些子问题，最后将子问题的解合并，得到原问题的解。

分治法是指将一个大问题分解成若干个规模较小的相似子问题，然后分别解决这些子问题，最后将子问题的解合并，得到原问题的解。

分治法在解决问题时，通常需要设计一个主函数（master function）和一个子函数（subfunction）。

主函数负责将问题分解，子函数负责解决子问题。

2.递归和分治法的区别递归法和分治法在解决问题时都采用了将问题分解成更小子问题的思路，但它们在实现上存在以下区别：（1）函数调用方式不同：递归法是通过调用自身来解决问题，而分治法是通过调用不同的子函数来解决问题。

（2）递归法必须有递归出口，即必须有一个基线条件，而分治法不一定需要。

3.递归和分治法的应用实例递归法应用广泛，例如斐波那契数列、汉诺塔问题、八皇后问题等。

分治法也有很多实际应用，例如快速排序、归并排序、大整数乘法等。

4.递归和分治法的优缺点递归法的优点是代码简单易懂，但缺点是容易产生大量的重复计算，导致时间复杂度较高。

分治法的优点是时间复杂度较低，但缺点是代码实现相对复杂，需要设计主函数和子函数。

总之，递归和分治法都是解决问题的有效方法，具体应用需要根据问题的特点来选择。

C三个柱子间移动。}
2023/10/8
计算机算法设计与分析
3
Hanoi塔问题的时间复杂性
n Hanoi塔问题的时间复杂性为O(2n)。 n 证明：对n归纳证明move(n) = 2n – 1。 n 归纳基础：当n = 1, move(1) = 1 = 21 – 1。 n 归纳假设：当n k, move(n) = 2n – 1。 n 归纳步骤：当n= k + 1，移动次数为
2、除法，即n / b，的形式
2023/11/4
计算机算法设计与分析
21
递归算法的时间复杂性
n 若~为减法，即n – b，则有：
T(n) = aT(n – b) + D(n)
= a(aT(n – 2b) + D(n – b)) + D(n) =
k–1
k–1
= akT(1) + ai D(n – ib) = ak + ai D(n – ib)
n q最(n简, m单)情{ 形1：(1) q(n, 1)=1, q(1, mn)==1 n或, mm≥1=;1 n 递q(iin归ff,((mnn关)<=系==1)：1q1)||(|((+|nm2(,)qmm<(qn=–(1,n1=)n,)–+1n1)q))(=rrnee–1ttmuu+rr,nqnm(01n);;, nnn＞–≤1m)m，＞n1＞1; n 产i生f (n的=新= 情1) 况|| (：n < m) return 1 + q(n, n–1); n (3r)eqtu(nr,nmq)(n=,qm(n–,1m) +–1q)(n+–qm(,nm–m);, m} ), n＞m＞1 n (整4)数q(nn的, m划)分= q数(nρ,(n),=nq＜(nm, n。)。

（⼀）⼋⼤算法思想⼋⼤算法⼋⼤算法：枚举、递推、递归、分治、贪⼼、试探法、动态迭代和模拟算法思想。

⼀、枚举算法思想（暴⼒算法） 将问题的所有可能答案⼀⼀列举，根据判断条件判断此答案是否合适，⼀般⽤循环实现。

经典运⽤：百钱买百鸡、填写运算符⼆、递推算法思想 1.顺推法：从已知条件出发，逐步推算出要解决问题的⽅法。

2.逆推法：从已知结果出发，⽤迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

经典运⽤：斐波那契数列（顺推法）、银⾏存款（逆推法）三、递归算法思想 1.递归过程⼀般通过函数或⼦过程实现； 2.递归算法在函数或⼦过程的内部，直接或间接调⽤⾃⼰的算法 3.递归算法实际上是把问题转化为规模缩⼩了的同类问题的⼦问题，然后再递归调⽤函数或过程来表⽰问题的解 注意：必须有⼀个明确的递归结束条件；如果递归次数过多，容易造成栈溢出。

经典运⽤：汉诺塔问题、阶乘问题四、分治算法思想 将⼀个规模为N的问题分解为K个规模较⼩的⼦问题，这些⼦问题相互独⽴且与原问题性质相同。

只要求出⼦问题的解，就可得到原问题的解。

⼀般步骤： 1.分解，将要解决的问题划分成若⼲个规模较⼩的同类问题 2.求解，当⼦问题划分得⾜够⼩时，⽤较简单的⽅法解决 3.合并，按原问题的要求，将⼦问题的解逐层合并构成原问题的解 经典运⽤：⼤数相乘问题、⽐赛⽇程安排五、贪⼼算法思想 从问题的某⼀个初始解出发，逐步逼近给定的⽬标，以便尽快求出更好的解。

局限： 不能保证最后的解是最优的； 不能求最⼤最⼩解问题； 只能求满⾜某些约束条件的可⾏解范围。

基本过程： 1.从问题的某⼀初始解出发 2.while能向给定总⽬标前进⼀步 3.求出可⾏解的⼀个解元素 4.由所有解元素组合成问题的⼀个可⾏解 经典运⽤：装箱问题、找零⽅案六、试探算法（回溯法） 在试探算法中，放弃当前候选解，并继续寻找下⼀个候选解的过程称为回溯。

扩⼤当前候选解的规模，以继续试探的过程称为向前试探。