chapter_computational_complexity/iteration_and_recursion/

[giscus[bot]]

chapter_computational_complexity/iteration_and_recursion/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_computational_complexity/iteration_and_recursion/

[orange-030]

k神加油

[krahets]

加油！

[gank1024]

如果能在代码块里加上代码行数字就更好了

[l0190]

其实迭代和递归就是数学归纳法，只不过一个是从前往后，一个是从后往前。

[cbingyao]

为啥Mac chrome下，数学公式都无法显示啊= =

[linlinsir]

可视化运行，是不是只能运行python代码啊，怎么切换啊，有没有友友们告知下

[SweetLove7s]

我算法小白理解的递归和尾递归，递归就好像是拿着个小本本，算一次，算不出答案，需要标记一下继续算，一直到最后一个答案算出来再根据标记往回总结答案，而尾递归则是算一次更新一下答案，所以到最后答案可以直接得出，这样的话感觉跟迭代很像啊

[SweetLove7s]

原来是这样，我以前从来不知道这个点，我觉得可以补充进文档诶

[krahets]

@SweetLove7s 很好的建议，我后面补一下

[SeaYJ]

@Rachel030219 我之前不知道在哪里说了句“所有的递归都能被写成迭代”，还被喷了...后来我就半信半疑。然后由此有个老师也说是错的，这句话我就彻底迷糊了。但是我一直愿意相信这句话是对的，却又不敢坚信这一点...

[samabl]

@SeaYJ 这句话是对的，系统执行递归调用本身就是压栈和出栈的循环，就像文中提到的模拟调用栈行为，如果有能力你可以将所有的递归写成显式的栈迭代

[Doub1e007]

看到这一下能理解尾递归了

[cbconne]

简单查了一下好像支持尾递归优化的语言不多，相对主流一些的语言 Java、Python、Go 之类的都不支持。

[Durantulax]

只知道刚学的scala支持

[ppwator]

go支持。时间上差异很大

[1244453393]

f(n)，f是什么意思

[1244453393]

我的意思是，文档是不是应该体现一下f的定义，包括下一章的T、O

[Shanndy]

设斐波那契数列的第 n个数字为 f(n)

[topul]

就跟数学中的函数 f(x)=y 是一个道理

[topul]

表达式"f(x) = y"表示一个数学函数。在这个表示法中：

• "f"是函数的名称。
• "x"是输入或自变量。
• "y"是输出或因变量。

这个表示法通常用于描述数学中输入变量"x"和输出变量"y"之间的关系。当你为"x"提供一个特定的值时，函数"f"将产生相应的"y"值。

例如，如果你有一个特定的函数，比如"f(x) = 2x"，你可以为"x"插入值以找到相应的"y"值。如果你将"x"设置为3，那么"f(3) = 2 * 3 = 6"，所以在这种情况下，"y"将等于6。

函数在数学中起着基础性的作用，用于描述代数、微积分和其他数学分支中的各种关系和操作。

[AnthemLights64]

对于初学者来说确实应该体现一下定义，作者在已知者角度容易将它作为基本常识。
f是函数的名字，n是函数接收的形式参数。

附带说一下，其实我想针对某条回复来回复的，不知道是作者还是这个架构的作者没有实现嵌套回复功能，可以考虑做一个

[l0190]

希望添加迭代器的代码

[krahets]

迭代器比较适合在特定的语言书里看，知道 for while 对于算法来说基本够用啦

[mtt3366]

我愿称之为最强教程。这一章终于完全理解了迭代和递归的不同，终于完全理解了尾递归。豁然开朗的爽感让我继续如饥似渴地阅读下面的内容！

[aksjfds]

python好像不支持 +=吧

[krahets]

@aksjfds Python 支持 += ，但不支持 ++ 。建议运行一下代码哦

[topul]

很多语言没有对尾递归进行优化，数据量不确定的情况下，用递归风险岂不是很大

[krahets]

所以我们要学习复杂度分析，估算递归最多使用多少空间与时间，以指导决策。而且，栈溢出也是经常遇到的情况 👀

[RachelMa-droid]

开头第一段话因为我不是很懂，所以去问了一下GPT，回复说：“迭代和递归都是程序中常见的控制结构，而不是程序结构本身。”这个回答是正确的吗？以及控制结构和程序结构的同异是什么呢？🤔

[wolf8334]

一本讲算法的书，没必要纠结这些相关度不高的概念。

[Jade-ps]

比作挖坑的话
迭代就是一边挖一边走，留下挖出来的土在坑旁边并记录。
递归就是挖一个坑 土留在坑旁边 然后去下一层地狱挖坑 然后土留在旁边 直到挖到第n层地狱 最后带着土上到地面称土有多重。

然后迭代解题关键就是计算好每次挖多少，迭代每次挖的土都是固定的重量，最后只管算挖了几次就能知道。
递归则是计算好每次比上次多挖多少，递归不管每次土有多重只管挖，最后一层层带着挖出来的所有土上到地面称土有多重，每一层都算一下，因为只有最后一两层知道土的重量。

迭代跟递归配合就是 在原地挖坑？不用往前走也不用去下一层 直接原地计算？有点迷糊了。

int fibonacci(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }

    int prev = 0;  // 第一个斐波那契数
    int current = 1;  // 第二个斐波那契数
    int result = 0;  // 存储计算的结果

    for (int i = 2; i <= n; ++i) {
        result = prev + current;
        prev = current;
        current = result;
    }

    return result;
}

chatgpt的迭代加递归 原地搞三个坑prev current result
运行规律就是 result称量总结和prev current土坑总共有多大 挖了多少土然后原地积累这些土，这些土。
接着prev复制current的 土坑规模 接着current 复制 result 的土坑规模。
这个复制过程用了递归的下地狱要点，因为能复制所以不用去下一层新的地方，重复这个过程则用了递归的记录每次比上次多挖了多少土的要点，每次都在同一个土地上霍霍，就逮着prev 土地和current 土地霍霍。不用去下一层土地，也不用去另一个位置。因为即知道每次挖多少土（规律），也知道截至目前一共挖出来多少土（求和)，更重要的是，不需要记录每次求和的数据，因为每次求和的数据都会被覆盖，挖出来的土一直在result这里堆着，不需要挖出那么多土坑，只需要两个土坑，一个result称量。
而result称量则是怎么记录每次都是多重呢，result每次记录就好像迭代 挖多少次 每次固定，只不过不再一个坑对应一堆土，算三次有三个坑留三堆土，它就在这个地方记了,每次增长的量可以被记录是因为增长的规律被定义了，增长是从已知的数增长的，每次增长的量也是已知的。

[Jade-ps]

但是用土坑解释斐波那契数列就有点难，一边在地面铲土一边在地狱下层数？地狱下到底拿到了实际数据之后就可以一层层上地狱直接上到地面？搞了个层数坑数个齐头并进？这样子好像不太必要，因为一带着数据一直往上走一层一层只算一次需要的实际的就好，那么别的地方多挖出来的坑位就算是平行世界，往上走的时候还要一个个填，可太费劲了，所以直接摧毁平整，或者不挖，但是位置要留着，这是不是就是递归算斐波那契数列占地多。虽然描述是这样，但是感觉有点硬是往概念上面靠拢的感觉了，不知道在计算机内存里这是怎么运行的。

[Jade-ps]

这个是个纯迭代呀 救命 chatgpt坑我。

[Jade-ps]

Chatgpt:您提供的程序使用了迭代，而不是递归的概念。尽管它模拟了斐波那契数列的递归定义（每个数是前两个数之和），但是它是使用循环来实现的，而不是通过递归函数调用来计算斐波那契数。

在递归中，一个函数会调用自身来解决较小规模的问题，而在迭代中，通过循环来逐步计算问题的解，而不需要递归调用。

在您的代码中，使用了一个循环来计算斐波那契数，这是一种典型的迭代方法。所以，尽管它模拟了斐波那契数列的递归定义，但它并没有使用递归函数调用，而是使用了迭代循环。

[Jade-ps]

然后如果这时候有个东西能够存起来每次递归计算出来的第n项数值，然后迭代的时候直接调用就好了，感觉跟老师讲的使用显式的栈模拟调用栈比较像.

[Neverforgetme]

谢了，刚好我和学生讲如何理解递归，就用这个下地狱的例子。

[sky508]

例如在以下代码中，条件变量，每轮进行了两次更新，这种情况就不太方便用 for 循环实现。

/* while 循环（两次更新） */
int whileLoopII(int n) {
    int res = 0;
    int i = 1; // 初始化条件变量
    // 循环求和 1, 4, ...
    while (i <= n) {
        res += i;
        // 更新条件变量
        i++;
        i *= 2;
    }
    return res;
}

这个地方提到用for循环不好实现，可是

int res = 0;
        for (int i1 = 1; i1 <= n; ) {
            res += i1;
            i1++;
            i1 *= 2;
        }

这样写也一样能实现的，感觉和while没啥大的区别

[krahets]

emmm 虽然都可以实现，但 for 和 while 还是有各自更适合的情况，一般不会硬凑

[AnthemLights64]

while和for互通的，但是在实际开发过程中，有逻辑上更适合的场景。常规的for循环多用于迭代和遍历，while循环常用于状态识别，如：while(!isBlocked) ，当isBlocked为false的时候，表示可以执行某些操作。各有好处。

[tron-robin]

语义上的不同吧，就像我可以喊部门老大x总（突出他在部门的身份），也可以喊他x哥（突出我和他的关系）

[m1crofan]

分治是一种算法设计思想，它通过将问题划分为多个相同或相似子问题，并分别解决这些子问题，最后将子问题的解合并起来得到原始问题的解。分治思想通常包括三个步骤：分解、解决和合并。

1. 分解（Divide）：将原问题划分为若干个规模较小、相互独立、与原问题相同或相似的子问题。这一步可以通过递归的方式进行。

2. 解决（Conquer）：递归地解决子问题。当问题足够小并可以直接解决时，递归停止。

3. 合并（Combine）：将子问题的解合并成原问题的解。这一步通常在递归的回溯过程中进行。

分治思想通常用于解决问题的规模较大、复杂度较高的情况，它可以将原问题划分为多个较小的子问题，从而简化原问题的求解过程。常见的应用包括归并排序、快速排序、二分搜索等。通过分治思想，可以提高算法的效率和可扩展性。分治是一种算法设计思想，它通过将问题划分为多个相同或相似子问题，并分别解决这些子问题，最后将子问题的解合并起来得到原始问题的解。分治思想通常包括三个步骤：分解、解决和合并。

1. 分解（Divide）：将原问题划分为若干个规模较小、相互独立、与原问题相同或相似的子问题。这一步可以通过递归的方式进行。

2. 解决（Conquer）：递归地解决子问题。当问题足够小并可以直接解决时，递归停止。

3. 合并（Combine）：将子问题的解合并成原问题的解。这一步通常在递归的回溯过程中进行。

分治思想通常用于解决问题的规模较大、复杂度较高的情况，它可以将原问题划分为多个较小的子问题，从而简化原问题的求解过程。常见的应用包括归并排序、快速排序、二分搜索等。通过分治思想，可以提高算法的效率和可扩展性。

[xlz1232]

”普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。”
这里我不太理解，为什么函数返回到上一层级的函数后，系统还需要保存上一层调用的下文信息，下文不是已经完成计算并返回了吗

[COCOXVI]

我也是小白，这是我的个人理解：
上一层级函数的返回值需要等下一层级函数的返回值计算完成并返回给它，它才能继续执行。
也就是说等下一层完成计算后，把返回值给到上一层，，上一层开始执行时相应的代码。正因为上一层是相较于下一层后计算的，所以才需要保存当时的上下文。
可以抽象的理解为递归是有“深度”的.QAQ

[COCOXVI]

在递归函数中，函数调用了自己本身，本质上是对函数自己的深层次的挖掘，所以我认为“下文”可能适当的理解成“深度”比较好。

[xlz1232]

感谢回答

[lurudong]

C#的命名有点不友好，
方法命名规则
forLoop->ForLoop
类
recursion.cs->Recursion.cs

[hpstory]

你好，部分格式和命名为了统一和方便维护，做了一些取舍，后面计划优先将方法名修改为PascalCase，相关的PR，谢谢。

[yeshuhao]

问在for循环中什么c++里面是++i，c中就是i++

[krahets]

在这里是可以等价替换的

[TaoShawn]

c++中++i比i++的性能更好，很多年不看cpp了，可以网上查一下原理

[yujiaqi0101]

请问，我用
def fib(n: int) -> int:
"""斐波那契数列：递归"""
# 终止条件 f(1) = 0, f(2) = 1
if n == 1 or n == 2:
return n - 1
# 递归调用 f(n) = f(n-1) + f(n-2)
res = fib(n - 1) + fib(n - 2)
# 返回结果 f(n)
return res

print(fib(4));

运行得到的结果是2，这和理解上的不一致，在本本上演算也是2，请问是哪里做的不对吗？

[yujiaqi0101]

懂了，是第N个数，不是累加，感谢。

[bart-fan]

应该理解为第一个数是1，而不是0，先决条件值错了

[yrrlxhj]

小白 不知道我理解的有没有错误：尾递归 就是在调用自身的同时，计算出当前调用层的结果，并且一起传递。这样 归 的时候 直接返回结果值。但是要返回n次

[ordinarycai]

return时会结束之前调用的空间，所以他只会用一个开辟的内存空间同时存在

[AtxxQvQ]

纯小白表示本书配合AI食用确实可以大大提升对于算法的理解🤩

[sharrk7mi]

刚看到递归，感觉绕进去绕晕了，但是根据断点和图表一步步跑，才明白原来是相当于从底层开始，从0,1,1,2 一直往上抛，感觉茅塞顿开，太感谢了

[WY202114]

请问普通递归是不是可以理解为，每次向下递一次，就需要在栈中保存一下该返回值，直到最后一次递归触发终止条件，开始一次一次的返回第一次递归所依赖的小结果，所以第一次递归的空间一直都不能释放。
尾递归是，每次递归，就已经将这次递归计算的结果以变量的形式传入到了下一次的递归中，就不需要在栈中保存。

[1647389319]

我理解普通递归，每次向下递的过程，不仅仅是需要保存该返回值，还有你这个函数后面还有需要执行的函数体代码。所以是不能销毁调用栈的。
而尾递归，不是说以变量的形式传入到了下一次的递归中。而是下一次递归的结果就是当前的返回值，而且当前函数体是执行完了，返回值也知道（下一次递归的值）。自然就没有必要维护其调用栈（调用栈保存的是当前函数执行的上下文信息）

[XXXX11XXXX]

我的理解是因为普通递归的求和是在归中，所以如果把上下文销毁了就不知道操作是什么了，因为你下一次归的动作还是需要那个上下文的，但是尾递归就是在递的过程中就已经结束了动作，归只需要把函数传下去就行了，所以可以直接传完删了上下文对总体动作不影响

[yiqiaos2023]

似懂非懂，小白第一天打卡。

[Aka-Edward]

打卡第二天！

[VitalFlare]

看不懂，晕了。我不如先去看后面的章节。

[L-130]

理解递归用了我一晚上。。。不知道后面还能不能把递归运用起来

[Charly168]

如果不去一步一步理解它的执行步骤，也没有太难。遇到递归题，只需要找到两个点就行了：规律+终止条件

[indestructible32]

感觉代码里的注释插在代码里有点乱，为什么不统一放在每行代码的右边的呢，代码和注释一左一右也条理清晰，符合习惯。

[Little27Rain]

看了评论区的讨论，于我本人而言最容易理解的方式是：函数运行到return后，就相当于把本次整个函数运行结束了，就可以释放存储空间了。所以尾递归的空间占用要比普通递归小。
（希望能得到大家的讨论与指导）

[Alexury]

Alexury打卡

[GStrong9005]

感觉好难理解啊😱

[njjnjjnjj]

加油！加油！

[MeloSydney]

递归可以用循环代替
递归本质上是编译器帮你做了栈处理
如果用循环做 需要自己设计数据结构和入栈出栈

[June0426]

简洁易懂！！我看课本和看各种的网课都不甚理解递归的底层原理到底是什么，看了这个真的一下子就懂了，k神我要誓死追随你

[wjyzoey]

ai写的斐波那契数列那个的尾递归：
def fib_tail(n: int, a: int = 0, b: int = 1) -> int:
"""斐波那契数列：尾递归实现"""
# 终止条件
if n == 1:
return a # f(1) = 0
if n == 2:
return b # f(2) = 1
return fib_tail(n - 1, b, a + b)
想问 if n == 1: 这个语句真的有必要写吗？

[hcat0616]

有必要，说一种最简单的情况就是输入是1，也就是第一位，如果没有if n==1，那就有问题了