虽然强者森林已经发文了，不过看到递回还是颇为手痒啊。 毕竟小时候相当喜欢递回，当然现在也是。 ---- 前情提要结束 ---- 递回，便是将原问题，切成相同但规模较小的问题，一一解决後便知原问题的答案了。 至於如何去解决，便是靠规模够小、无法再分割时的答案，而这也是我们已知的。 而函数呢，看它是什麽型态，便可以将其视为该型态的一个数值， 其数值则视传入参数与运算方式等等而定。 举个老例子，计算 n! 为何。 已知 n! = (n-1)! * n，因此我们只要知道 (n-1)!，就可以知道 n! 的答案。 假设 f(i) 可以正确求出 i! 的值，於是在计算 n! 时， 只要先用 f() 计算 (n-1)! 的值，再将其乘上 n，即为所求。 这时会将切割後的子问题 (n-1)! 当作一个相同，但规模较小的独立问题来做。 而这个独立问题，设 m = n-1，则等同於求 f(m)，即 m! 的值。 这又会求 (m-1)! 的答案，以算出 m!，所以变成了一样的问题。 但是前面只是假设正确，它真的正确吗？ 已知 0! = 1，而若 i! 正确，(i+1)! = i! * (i+1) 也会是正确的， 所以这样写是正确的。 而实际程式在执行时，流程是这样子的： 假设我们呼叫了…不要太大，f(4) 就好。还和某首 debug 神歌有异曲同工之妙。 /* 以下 code 省略一些不太重要的东西 */ main() { printf("%d\n", f(4)); } 可是要输出之前，必须先算出 f(4) 的值为何。因此，main() 会呼叫 f(4)， 并等待其算完，否则无法继续下去。 f(n) { if(n == 0) return 1; return f(n-1) * n; } 现在要计算 f(4)，而 main() 正在等待结果。 想像你正在对抗强大的使徒，却孤立无援，只好求助於平日好朋友 f(4)。 这里你可能会质疑我，说不定强者我同学就会了，那干嘛继续递回下去？ 想像你的朋友会解你问题的大部份，却有一些小地方不懂得怎麽解； 於是他再去问他朋友他不懂的地方，而他朋友在他不懂的地方也有一些不会解， 只好再去问朋友，… 将这些朋友依序由大到小编号 4~0 好了。 直到问到最後一个人 0，他成功把所有小疑问解答出来了， 则 1 问到这些小细节後，他也把 2 所提的问题全解答出来了。 2 问到他所不会的小地方後，也把 3 问他的全解出来了。 在 3 告诉了 4 怎麽解 4 卡住的地方後，4 也成功解出你所不会的地方； 於是你就 AC 啦！ 运行过程如下： f(4) <== 现在在这里想办法求 f(4) main() /* 想像它们叠起来了，而我们得从最上面慢慢处理 */ /* 想像你是 main()，正等着 f(4) 解出你的问题，并告诉你。 */ 但我们不知道 4!，幸好我们知道可以先求 3!。 想像 4 在你提问的问题中，有一些不会解，只好问 3。 於是变成这样： f(3) <== 现在在这里 f(4) <== 等待 f(3) main() <== 等待 f(4) 可是 3 也必须求助於 2 才行，所以只好… f(2) <== 现在在这里 f(3) f(4) main() 可是 2 也还不知道呢…不拖戏，直接继续： f(1) <== 现在在这里 f(2) f(3) f(4) main() 於是求助於 1 f(0) <== 现在在这里 f(1) f(2) f(3) f(4) main() f(0) 终於所有问题都会，而不用再去问其它朋友啦！ 於是 f(0) 将答案告诉 f(1)，而 f(0) 的答案是 1。 f(1) <== f(0) 告诉他卡住的地方怎麽解後，就秒杀了，再告诉 f(2) f(2) f(3) f(4) main() 当 f(1) 告诉 f(2) 怎麽解 f(2) 所卡住的部份後，也就完全解决了 f(3) 的问题。 f(2) <== 在这里解决後，告诉 f(3) f(3) f(4) main() 接着换 f(3) 问到卡住的地方後，解决了 f(4) 的问题了。 f(3) <== 也解决了，告诉 f(4)。 f(4) main() f(4) 在问过 f(3) 他卡住的一小部份後，也把你发问的问题给全部解决啦。 f(4) <== 解决，告诉你。 main() 於是回到 main()，而你在得到解答後便 AC 啦。 在这里，f() 的规模越来越小，但都是相同的。 可能你一开始有 10 题不会，但到後面可能只剩 3 题、1 题、…，直到被全解。 也许 f(4) 只去问了 f(3) 共 7 题，但不先问到，也没办法完全解开； f(3) 只需要会那 7 题，但可能有个 4 题不会，也得先问到才算完全解开。 也许 f(0) 只需要会 1 题就好，但那是极关键。知道它後，连带的可以知道许多； 递回的运行，差不多就是这样子的。 另外丢个小问题给大家玩玩看好了。 如果告诉你 n 并给你 n 个数，怎麽求最小值为何呢？ 以下附解答，慎入。 已知这 n 个数的最小值，要嘛在第 n 个数，要嘛在前 n-1 个数中。 於是我们可以将前 n-1 个数求最小值，看作一个新的 n 数求最小值问题。 已知若 n 为 1，则最小值即为该数；由此可知递回式如下： （设此 n 数为 a[1] ~ a[n]） f(1) = a[1]; f(n) = min(a[n], f(n-1)); 贴心文末防雷空页。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.240.202