小蝠猫学算法#1——迭代和递归

文章寄语

且视他人之疑目如盏盏鬼火，大胆地去走你的夜路。
　　　　　　　　　　　　　　　　　　　　—— 史铁生<<病隙碎笔>>

引言

这里是新开的坑！以后会把关于数据结构与算法的知识笔记写在这里

数据结构笔记第一篇。迭代和递归[考纲无此内容]

知识点大致按照《Hello!算法》书籍进行。因为数据结构与算法在非常多的考试中都有。

本人自知学疏才浅，一定有许多错误，恳请批评指正。

下面是几个上述提到的链接：

《Hello!算法》网页版全国计二级官网洛谷官网-刷题可用

星空如此璀璨，想摘几颗星星。出发吧

第一节迭代和递归

迭代

迭代(for结构)

迭代在汉语词典中的大概意思是”更相代替；轮换”。生活中也能听到类似”电子产品迭代更新”的话语.

在计算机里也是如此，它是一种重复执行某个任务的东西，一直运行直到条件不满足。

在现实中大概可以想象成把书放上书架，书还没放完就继续放，放完了就停止。

如果提前知道有几本书需要放置，就可以使用for结构。每次放上一本书后，都需要看看还有没有书。所以判断了n(书籍数量)次。

int forloop(int n)
{
    //原来书堆里有几本书？假设是5本
    int bookheap = 5；
    //有5本书就是放置5次呗。
    //i值任取，只要次数对就行。但为了看着舒服，i还是从0开始计数把。
    for(int i = 0; i < 5; ++i)
    {
        //放好一本书时，书堆的书就少一本。
        bookheap--;
    }
    return bookheap; 
}

放好了，书堆里没有书了(归0),跳出循环同时程序结束。(虽然这段代码有点莫名其妙,说不定以后我变笨蛋了还可以看看x)

迭代(while结构)

还是那一包书，但现在状况变了，我不知道这一包书到底有多少本，我懒得数。也就是不知道有几本书需要放置，这就可以用while结构。

这种办法是放完就停。但每次放上一本书后，也是需要看看还有没有书的。所以同样也是判断了n(书籍数量)次。

int forloop(int n)
{
    //原来书堆里有几本书？
    int bookheap = n；
    //书堆里还有书的话就继续放
    while(bookheap > 0)
    {
        //放好一本书时，书堆的书就少一本。
        bookheap--;
    }
    return bookheap;
}

放好了，书堆里没有书了(归0),跳出循环同时程序结束。

两个循环的区别:

①for偏向紧凑，变量i和模具一样限制死了。while偏向灵活，可以拿捏变量i(比如先加再乘这种for不好操作的)
②在知道操作次数的情况下，for的代码比while简洁，避免大量计数器和flag等变量出现。
③大部分情况两者差不多，按实际情况判断。
for要写三个条件，本来就长，有时候条件复杂点更长。真不如while().

迭代(嵌套)

纯套娃，一般套娃都是用变量i和j搞定。就两层娃。

把它看成长方形就好了，或者看成表格。你要数格子的话，总是长(格子数)*宽(格子数)把？所以需要判断[i的终值*j的终值]次。

如果它还能套，套套套甚至把26个字母都用完了(那确实有点),那也没关系，把它26个字母所代表的变量的终值全部乘起来就好了。

那这个算是，26维物体了，我找不到例子。假如i是1-5，j是1-6，k是1-7的话，就是判断了5*6*7次。

递归

迭代在前面比较简单，但是递归要考虑的就很多了。

递归的意义

递归就是调用自己本身,递归类似套娃循环也有深度一说，且深度过大会导致栈溢出问题。

它主要由两部分组成：

递归的递，把东西传递到最深度。
递归的归，把东西从最深处加工后送出来。

就和工厂里某个产品的制作工序一样。放入原料，送入机器最里层，从里到外逐层加工。

但是必须要有结束条件，如果没有结束条件，他会一直运行下去。

int recur(int n) {
    // 这个是终止条件
    if (n == 1)
        return 1;
    // 把原料送进去
    int res = recur(n - 1);
    // 加工后吐出成品
    return n + res;
}

调用栈操作

函数在没有返回最终结果之前，每一层都会占用内存。这个占用叫栈帧空间，函数最终返回后释放。

因为栈分到的内存是有限的，如果占满了就栈溢出了。

尾递归使用

如果函数在返回前的最后一句才调用，也就是把递归写在return里，就可以被软件(编译器)优化。从而节省了开销。(其实没用，大部分软件没法优化，仅是理论上而言)

而普通递归呢，就是写在return前面，会捞一点，因为要先操作(递)，在返回过程中(归)还要操作。不如尾递归，它只要操作后(递)直接返回就行，不用额外操作。

递归树使用

其实递归的本质就是把大东西切分成小东西。和把问题简单化的分治一致。

就和斐波那契数列一样，因为第n项是由前两项的和而来的，所以是两条分支。

而这两条分支的子节点又是由前两项的和而来的，所以又可以分成两条支线，最后变成一棵庞大的树。

其实，这棵树不仅是递归树，我感觉还是满二叉树？

迭代/递归对比

其实两个之间也差不多。

迭代和递归区别:

①迭代没有调用的开销；递归每次调用都有时间开销。
②迭代有固定调用次数；递归不确定，按深度计算。可能非常大.

书籍上还提到了递归和栈之间的联系。说什么先入后出和栈帧这种难懂的东西。

我的理解是就像一个车床要加工木棍，你得先把原材料(一根木头)放进去。

放进去的过程中木棒会占用车床的内部空间，也就是逐渐开辟内存的过程。同时这也是”递”的过程。

然后机器会开始加工。这时候原来放进去的”头”就会变成”尾”。且加工途中不会返回去处理处理好的部分。

加工完毕以后需要把产物退回。这时车床的内部空间就被腾出来了。即逐渐恢复内存空间的过程，同时这也是”归”的过程。

因为车床底部是封死的，不是中空的。所以这种工作机制也就是“先入后出”。(中空的”先入先出”为队列)

总结和结语

文章结语

让我成为你的双眼，把那世界万千，描绘在你面前。
　　　　　　　　　　　　　　　　　　　　——狐妖小红娘

笔记完毕编辑完毕时间CST 6.28 02:51

最后修改于8.15 00:30

蝠池茶园