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

文章寄语

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

引言

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

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

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

本人基础较弱，可能会有许多错误，恳请批评指正。

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

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

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

第一节迭代和递归

迭代

迭代(for结构)

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

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

可以想象一下把书放上书架，书还没放完就继续放，放完了就停止。

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

//原来书堆里有几本书？假设是5本
int bookheap = 5；
for(int i = 0; i < 5; ++i)
{
    //放好一本书，书堆的书就少一本。
    bookheap--;
}

放好了，书堆里没有书了,程序结束.

迭代(while结构)

还是那一包书，但现在不知道这一包书到底有几本.也就是不知道有几本书需要放，可以用while结构。

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

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

放好了，书堆里没有书了,程序结束。

两个循环的区别:

for偏向紧凑，while偏向灵活.while可以拿捏变量,先加再乘这种for不好操作的.
知道操作数的情况下，for的代码比while简洁.

迭代(嵌套)

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

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

如果它还能甚至把26个字母都用完了，那也没关系，把它26个字母全部乘起来就好了。

递归

递归的意义

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

它主要由两部分组成：递归的递，把东西传递到最深处。递归的归，把东西从最深处加工后送出来。

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

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

int recur(int n) {
    // 这个是终止条件
    if (n == 1)
        return 1;
    // 送原料
    int res = recur(n - 1);
    // 吐产物
    return n + res;
}

调用栈操作

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

因为栈分到的内存是有限的，如果它把自己都内存占满了还没有返回结果，就栈溢出了。

尾递归使用

如果函数在返回前的最后一句才调用，就可以被编译器优化。从而节省了开销。而普通递归会捞一点，因为要先操作，在返回过程中还要操作。

递归树使用

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

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

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

迭代/递归对比

迭代和递归区别:

迭代没有调用的开销；而递归每次调用都有时间开销。
迭代有固定调用次数；递归不确定且可能非常大.

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

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

放进去的过程中木棒会占用车床的内部空间，也就是逐渐开辟内存的过程。占用的这部分空间就叫栈帧空间。

为了保持效率，生产过程必定是一边放入一边加工的，慢慢将原料完全放入也就是”递”的过程。

加工完毕将产物吐出。这时车床的内部空间会慢慢恢复。释放被占用的空间。同时这也是”归”的过程。

因为车床底部是封死的。原料是头部的先入，但产物出来却在尾部。所以这种工作机制也就是“先入后出”。

结语

文章结语

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

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

最后修改于9.27 19:00

蝠池茶园