0 回顧

之前的筆記（0）和筆記（1），我們介紹了算法的基本含義，并且舉了一些實(shí)例，同時(shí)理解了，算法就是人類在教計(jì)算機(jī)做事情！

我們知道，算法就是解決問題的方案，我們將自然語言描述的問題，轉(zhuǎn)換為符號(hào)語言，再解決問題，使用計(jì)算機(jī)思維，構(gòu)建解決問題的算法，最后轉(zhuǎn)換為計(jì)算機(jī)可以識(shí)別的語言，教會(huì)計(jì)算機(jī)，讓它幫助我們解決問題。

在算法設(shè)計(jì)的時(shí)候，我們需要關(guān)注其時(shí)間和空間的復(fù)雜度，這與實(shí)際問題有關(guān)，可能關(guān)注事件，也可能關(guān)注空間，也可能二者兼有。

下面，我們來看看遞歸思想，并且使用實(shí)例來理解抽象的思想。

1 遞歸思想

遞歸是可能計(jì)算機(jī)與人類最大的不同，人類是遞推思維，能夠發(fā)散，計(jì)算機(jī)是遞歸思維，能夠做重復(fù)且簡(jiǎn)單的固定事情。

因此，我們教計(jì)算機(jī)做事的時(shí)候，要盡可能簡(jiǎn)單且固定，也就是，我們需要將一個(gè)復(fù)雜的問題，拆解成若干小問題，這些小問題最好還是已知的，已經(jīng)被解決的，這樣，我們就很容易能夠設(shè)計(jì)出一個(gè)算法，并且教會(huì)計(jì)算機(jī)做事。

1.1 遞歸的含義

所謂的遞歸，看起來就像：同樣的一件事情，做了很多遍，雖然每一次的代碼一樣，但是每一次的數(shù)據(jù)不一樣，導(dǎo)致行為不一樣，并且，會(huì)有一個(gè)盡頭，一旦走到盡頭了，就得原路返回來。

我們看一個(gè)例子

#include <iostream> using namespace std;void story(int i) {if (i > 10)return;cout << "從前有個(gè)廟，廟里有個(gè)老和尚，老和尚給小和尚講故事" << endl;cout << "講的故事是什么呢？講的是：" << endl;story(i + 1); }int main() {story(1);return 0; }

這就是生活中的一個(gè)遞歸的例子，還蠻有趣的！

注意，它并不是循環(huán)！與循環(huán)還是有差別的，最重要的就是，遞歸在條件終止之后，會(huì)返回來，而循環(huán)，條件終止就停了。

1.2 遞歸算法的重要結(jié)構(gòu)

終止條件 & 終止處理辦法

遞歸處理方法

我們知道，遞歸不可能無限進(jìn)行下去，因此需要終止條件，以及觸發(fā)該條件后對(duì)應(yīng)的處理方案。

并且，更重要的是，我們需要知道遞歸如何處理。

對(duì)于遞歸程序，通常都是解決一個(gè)小問題。

我們將一個(gè)大問題分解成若干個(gè)小問題，然后，這些小問題的處理方式是相似的，我們用遞歸來分別解決每一個(gè)小問題，得到每個(gè)小問題的解，之后將這些解合并。

階乘問題

先列出遞歸方程，再轉(zhuǎn)換為程序即可。

// 階乘問題 int factorial(int n) {if (n <= 0)return 1;elsereturn n * factorial(n - 1); }

如果不用遞歸呢？

使用遞推！ 從1到n.用循環(huán)搞定。

// 不用recursion的階乘，遞推 int factorial2(int n) {if (n == 0)return 1;int result = 1;for (int i = 1; i <= n; i++) {result *= i;}return result; }

遞歸特點(diǎn)：有去有回！從n到1！從結(jié)果到起點(diǎn)，再返回來。

對(duì)于遞歸來說，最開始目標(biāo)的n就是已知的，然后逐漸變化到臨界值，經(jīng)過層層處理，再返回來。關(guān)鍵點(diǎn)：遞歸方程！

斐波那契數(shù)列

遞歸方程

f(n) = 1，n = 1或n = 0

f(n) = f(n-1) + f(n-2)，n > 1

// 斐波那契數(shù)列 int fib(int n) {if (n == 1 || n == 0)return 1;return fib(n - 1) + fib(n - 2); }

迭代：就是重復(fù)執(zhí)行一些指令，指令是一定的，但是相關(guān)的數(shù)據(jù)是變化的。

遞歸調(diào)用的過程，終點(diǎn)參數(shù)在不斷變化，一直在逼近終點(diǎn)，最終停下來，依次返回。

小結(jié)

我們先將一個(gè)問題，使用符號(hào)語言描述，拆解問題，將其轉(zhuǎn)換成遞歸方程，使用數(shù)學(xué)語言描述，然后將其轉(zhuǎn)換為算法和實(shí)際的程序。

所謂的遞歸，就是先給出終點(diǎn)參數(shù)，它是復(fù)雜的，然后隨著參數(shù)的減小，會(huì)逐漸簡(jiǎn)單，然后得到最簡(jiǎn)單的結(jié)果，之后再往回走，就能獲得復(fù)雜問題的結(jié)果。

這與人類思維不一樣，人類通常是遞推，先解決簡(jiǎn)單問題，再逐漸復(fù)雜化，最終解決復(fù)雜問題。

因此，求解問題的時(shí)候，可以簡(jiǎn)單問題找規(guī)律，最終獲得復(fù)雜抽象的方程，從而獲得最終結(jié)果。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【算法】学习笔记（2）：递归思想的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。