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个数，不是累加，感谢。

[shangli-23]

为什么尾递归返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。我没有理解，它和普通递归不是都开辟了保持数据的空间吗？

[krahets]

由于“无须继续执行其他操作”，因此系统就不用暂存上一层函数中的各项数据了，因为用不上这些数据了

[dream-TechG]

普通递归返回上一层后还需要被保存下来，进行计算，才能接着返回
在尾递归中就不需要被保存，一直返回就可以

[Neverforgetme]

K神仙《显式的栈》 过于抽象
我们可以使用一个显式的栈来模拟调用栈的行为，从而将递归转化为迭代形式。
这一块能不能详细讲讲，确实看不懂？

[mmengjiadai]

我感觉可以这样理解：递归的时候会一次调用n，n-1，...，0的递归函数，每次调用一个新函数的时候会给这个新函数分配一个栈（调用的时候不会执行函数，全部执行完之后再开始倒序执行函数并返回值），这个分配的过程对应于作者写的迭代代码里的stack.append()部分，作者显示定义的stack里的项和迭代函数的返回值一样。之后从最后一个分配的栈开始执行函数并累加返回值，对应显示定义的stack.pop()过程。
个人理解，欢迎讨论～

[binjiangdao]

2.2.2下面有递归的可视化运行，里面就体现了递归中栈的使用。显示的栈就是用循环和栈模拟这种过程。栈保存了每次基本操作时的数据。

[Neverforgetme]

牛逼的

[MambaFly]

头一次这么清晰的透彻理解递归，终止-递-归，突然发现递归这个词用的太明晰了，原来递归和迭代可以通过栈作为桥梁来联系啊！

[dream-TechG]

我是集成电路转行ai，目前在疯狂补基础知识，花了半个多小时把截止到这一小节的知识看完了，感觉收获很大
还有好多cs的基础要补，任重而道远

[zhanglei1032]

计算机都快卷成花卷了，还是搞芯片实在

[dream-TechG]

我也想接着搞ic，但是现在老师是做ai的，直接一个大跨行

[T00ler]

图 2-5 尾递归过程，为什么“归”那里要写好多层，不是只走一遍就结束了吗。

[T00ler]

好像看明白了，虽然说返回的是同一个东西但还得要一层一层往上返回XD

[dream-TechG]

尾递归还是给函数分配了空间，需要一个一个函数这样一层层先把数值传递回去，最后才把求的数值res输出
不知道这样理解对不对

[T00ler]

我开始也是这么想的，但貌似不准确。我结合了一下文章和GPT的解答，理解如下：
尾递归在直观上确实给函数分配了额外的空间，但在经过某些编译器或解释器的优化后则不再需要为其分配额外的空间，这种优化会使得每一层的函数共用一个栈空间。你这个理解是没问题的，只是第一句话在某些情况下会进行优化。

[Xinkun666]

因为有return呀

[T00ler]

普通递归和尾递归在代码层面上是不是可以这么理解，只要return的东西是递归函数本身，那就是尾递归，否则为普通递归。

[Ycloud2024]

尾递归：递归调用是函数返回前的最后一个操作（它的返回值不属于表达式的一部分）。个人感觉，加上括号里的话可能更好理解一点。文中的普通递归，在函数的递归调用和返回之间，还进行了一次加法操作，因此还需要给n分配空间。

[esv0t10n]

嵌套循环：注释：n * n 为对应点数量，"(i, j), " 对应字符串长最大为 6+102，加上最后一个空字符 \0 的额外空间
想知道这里的注释是啥意思，6 以及 102分别是啥

[BLackWatch1118]

这行snprintf(tmp, sizeof(tmp), "(%d, %d), ", i, j);, 意思是将i，j 转化成格式字符串(i, j), 的形式(这里的每个逗号之后都有一个空格)，并将字符串复制到tmp中。因为i,j 都是int类型，最大值2147483647有10位，转换成数字字符共需要10个字节，2个数就是10 x 2（不是102），每个符号占一个字节，包括空格，共2个括号、两个逗号和2个空格，所以一共6个字节。所以储存(i, j), 格式的字符串需要2*10+6个字节。

[esv0t10n]

大佬，太感谢了！这个时候 2147483647 每一位都是一个独立的字符而不是代表一个整体的数字，所以一共就10位所以就是10，i和j就是20个字符需要20个字节对吗？

[BLackWatch1118]

不算大佬，这个就是要把数字转化成字符串的形式，每一位都需要单独表示为一个数字字符，有几位就要几个字节

[NgxuAnGMH]

个人小结：
1、迭代：for while，for 更加固定，while 将条件变量的变化写在内部进行处理，更加灵活。
2、递归：递和归，适合分解问题（链表/树/图），但对内存空间要求更高，调用栈也有可能产生溢出错误。

• 尾递归 / 普通递归：编译器或解释器是否支持优化。
• 递归深度 / 递归树：算法层面，搜索/排序/回溯/分治/动态规划，用到这种思维。

[sundayha]

既然是斐波那契数列，那我就用 go 的内存缓存实现一个Fib(500)秒出的例子吧

var fibs [800]uint64

func Fib(n int) uint64 {
	var res uint64
	// 终止条件
	if fibs[n] > 0 || n == 0 {
		return fibs[n]
	}
	// 终止条件
	if n <= 2 {
		res = uint64(n - 1)
		return res
	} else {
		// 递与归
		res = Fib(n-1) + Fib(n-2)
	}
	fibs[n] = res
	return res
}

[iHugo-Tang]

感谢！第一次觉得尾递归，递归转换成迭代这么容易理解。

[wxamlzm]

力扣对应部分的算法题，递归和回溯部分，反向看答案到思路是能看懂的，但正向自己去推导，有时候能推导出中文思路，但是没法构想出递归方程式TAT

[zhuyihuan68]

读题找变量 找出变量之间的关系规律 转化成代码

[WillFu82]

For(int i=0 ; i<n ; i=(i+1)*2 ){}这种写法也是成立的。for循环的第三个表达式可以看成是循环体内的最后一个语句。所以例子跟结论不怎么对应。但意思我理解了，也知道怎么用。
主要学算法和结构，加油。

[krahets]

确实体现的不够明显。可以稍微调换一下代码顺序，就会发现用 for 更难实现了：

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

逻辑越复杂，while 的灵活性就体现的越显著。

[Contin-KD]

5.22打卡

[LeeDota2]

24.5.23打卡！