[其它]C语言课件第9部分 递归程序设计.ppt

第九部分 递归程序设计技术 学习程序设计需要注意规律性的东西 本章内容 递归与循环 递归函数的执行过程 递归函数效率 循环与递归 循环程序 用于描述需要重复进行计算 高级语言里，也常见用递归来实现重复的计算。 递归—recursion, recursive algorithm 函数或过程调用自身 C语言允许递归，可以在函数内调用自身，常常使程序更简单清晰。 1. 阶乘和乘幂 例：定义计算整数阶乘的函数 1×2×…×(n - 1)×n 本例中，乘的次数依赖于n，计算所需的次数定义时无法确定。 这是一种典型循环情况 计算“次数”依赖某些参数的值。 程序 long fact1(long n) { long fac, i; for (fac = 1, i = 1; i = n; i++) fac *= i; return fac; } 阶乘函数的精确定义 是一种递归定义的形式 要解决规模为n的问题，要先解决规模为n-1的子问题，依此类推。 如果高级语言允许递归定义函数，就可以直接翻译为程序。 C允许递归定义 在函数定义内直接或间接地调用被定义函数本身。 写成递归函数 long fact (long n) { return n == 0 ? 1 : n * fact(n-1); } long fact(long n) { if (n = 1) return 1; return n * fact(n - 1); } 递归与计算过程 包含递归的程序产生的计算过程和性质更复杂，能完成很复杂的工作。 递归调用只有一个调用表达式或语句，但是可能要许多步才能完成。 实际参数的不同，会实际产生的递归调用次数（步数）也会有很大的不同。 递归程序理解的理解比较困难 递归的函数定义需要有条件语句去控制递归过程的最终结束 直接给出结果的时候，递归结束； 把对较复杂情况的计算归结为对更简单情况的计算，需要进行递归处理。 递归和循环 基本运算、关系判断、条件表达式，加函数定义和递归定义构成了一个（理论上）“足够强的”的程序语言。 循环程序可以改成递归实现 递归程序也可以改成循环实现 2. Fibonacci序列 计算与时间 定义 Fibonacci（斐波那契）序列的递归定义 F0 = 1, F1 = 1 Fn = Fn - 1 + Fn - 2 (n 1) 1, 1, 2, 3, 5, 8, 13, 21, 34, 65, 99, … 用递归程序实现 long fib (int n) { return n 2 ? 1 : fib(n - 1) + fib(n - 2); } 例fib(5)调用过程 问题 存在大量重复计算，参数越大重复计算越多。 有关系吗？ 随着参数增大，计算中重复增长迅速，最快的微机上一分钟大约可以算出fib(45) 参数加1，fib多用近一倍时间(指数增长)。最快的微机一小时算不出fib(55)，算fib(100)要数万年 计算需要时间，复杂计算需要很长时间。这是计算机的本质特征和弱点。说明它不是万能，有些事情“不能”做。 计算复杂度 人们发现了许多实际问题，理论上说可用计算机解决（可写出计算它的程序），但对规模大的情况（“大的参数 n”），人类永远等不到计算完成。 这时能说问题解决了吗？ 计算中有一大类问题被称为的“难解问题”，其中有许多很实际的问题，如规划、调度、优化等。 解决这些问题，需要理论和实际技术的研究。 另外，对于许多问题的实用的有效算法，有极大的理论价值和实际价值。 计算复杂性，难解问题，“P = NP？”问题。 阅读材料：NP问题/NP-Problem.html A problem is assigned to the NP (nondeterministic polynomial time) class if it is solvable in polynomial time by a nondeterministic Turing machine. A P-problem (whose solution time is bounded by a polynomial) is always also NP. If a problem is known to be NP, and a solution to the problem is somehow known, then demonstrating the correctness of the solution can always be reduced to a single P (polynomial time) verification. If P a