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，先决条件值错了

[Distance812]

请问为什么我的VScode控制台运行结果乱码？如何解决呢？谢谢大佬
显示结果如下：

for ѭ������ͽ�� res = 15

while ѭ������ͽ�� res = 15

while ѭ�������θ��£���ͽ�� res = 5

˫�� for ѭ���ı������ (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), 

[Distance812]

补充：使用的是Code Runner插件

[Distance812]

已解决！

引用博客：解决VS Code使用code runner开发Python乱码问题 - clemente - 博客园 (cnblogs.com)

方法有两种 我用的是第一种 第二种自行尝试 方法在上面链接
方法步骤为：右下角设置->选择设置->在左侧选择扩展->找到Run Code configuration->随便点击一个在settings.json中编辑能进入settings.json配置文件的按钮->删除掉VScode新增出来的代码（删不删都行）->在一级大括号下新增"code-runner.runInTerminal": true,->保存并关闭->测试是否成功

[JX7746]

听懂了!很nice

import matplotlib.pyplot as plt

def for_loop_recur(n:int) -> int:
    # 使用迭代模拟递归
    stack = []
    res = 0
    accumulation_values = []# 记录每次累加值
    
    for i in range(n,0,-1):
        stack.append(i) # 此时传入的同时栈的长度被n规定
        
    while stack:
        # 使用res累加，pop推出栈底获取累加结果
        res += stack.pop()
        accumulation_values.append(res)
        
    return res, accumulation_values
    n = 100
out, accumulation_values = for_loop_recur(n)
print(f"最终累加结果为：{out}")
#for i in range(1,n,5):
#    print(accumulation_values[i])
x = list(range(1, len(accumulation_values) + 1))
# 绘制折线图
plt.plot(x, accumulation_values, marker='o')

# 设置图表标题和坐标轴标签
plt.title('Data Over Time')
plt.xlabel('Time (Index)')
plt.ylabel(accumulation_values)

# 显示网格
plt.grid(True)

# 显示图表
plt.show()

[JX7746]

很怪，部分以代码形式发布了，但是部分没有

[va226]

不太懂

[JX7746]

可能是我代码不太规范，太菜了

[JiangJC253]

哈哈哈，不是的。这个文字框是markdown格式的，你的井号正好对应md里面的一级标题，所以自动放大了

[769174850]

markdown语法这是，可以去看一下

[Zhao-Yi-Ya]

/* 双层 for 循环 */
char *nestedForLoop(int n) {
    // n * n 为对应点数量，"(i, j), " 对应字符串长最大为 6+10*2，加上最后一个空字符 \0 的额外空间
    int size = n * n * 26 + 1;
    char *res = malloc(size * sizeof(char));
    // 循环 i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; i++) {
        // 循环 j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; j++) {
            char tmp[26];
            snprintf(tmp, sizeof(tmp), "(%d, %d), ", i, j);
            strncat(res, tmp, size - strlen(res) - 1);
        }
    }
    return res;
}

这个双重循环代码，我认为在snprintf这个函数这里有点问题，snprintf函数第二个参数size，是当字符串
长度>=size时会将size-1个字符放到缓冲区，留一个位置给\0，当i，j都为10位数时加上格式化表示形式刚好等于26个字符，所以最后的输出中会有一部分字符串表示为“(i, j),(i, j),...”,跟预期的表示形式相比两个坐标之间会缺少了空格，所以我认为这里申请tmp数组时长度写为27比较好，当然这个不会影响结果也只是表示形式的不同，只是个人见解虽然这个见解没什么用

[Chouyangt]

脑子会炸了

[goodluckily]

已经懵了

[oneandonlycharlie]

关于斐波那契数列的例子里有多少层的问题，可以看CS61A讲义里的图解，更准确，这个递归树并不是严格对称的，因为第0，1，2个数字并不遵循后面的递进规律，但是递归的逻辑是一样的，需要层层递进。https://cs61a.org/disc/disc04/disc04.pdf

[Ca11me1ce]

你好，我觉得新手（我）从“递归”往“尾递归”转换有点难度，需要一些时间去思考
是不是尾递归在递归的同时，把结果存储也递给上层和下层，这样结束一层不需要存储它的上下文？
终止条件的定义也有点难懂，也需要一些时间思考。
写出递归的范式（执行步骤）最难了

[Ca11me1ce]

第一遍 8/26/2024 7:15PM San Francisco 打卡
会回来看第二遍

[hakunamatata19]

终止条件就是 那个我们已知结果的条件， 比如对于斐波纳契数列来说，我们知道要求 f(n), 但是我们知道 f(1) =1 f(2) =2, 基本思想就是： 我们 要求f(n) ,但是太难了，我们一步一步将他转化成 求 f(n-1), f(n-2), .... 最后变成求 f(2), f(1)

[xia0xiong]

關於 递归 调用栈的描述疑問：

１．函数的上下文数据都存储在称为“栈帧空间”的内存区域中，直至函数返回后才会被释放。因此，递归通常比迭代＂更加耗费内存空间＂。
２．递归调用函数会产生额外的开销。因此递归通常比循环的＂时间效率更低＂。

為什麼最後的結論是时间效率更低，而不是繼承前一點脈絡為空間效率更低

[yatyu]

这是两句独立的话。
1.因为递归有栈帧空间的存在，所以更加耗费内存说的就是空间效率较低。
2.因为递归会产生额外的开销（计算开销），所以时间效率较低。

[jokerdragon76]

我的可视化运行程序怎么是空的，没有展示

[Fe1H]

网络不好，没有加载出来，我这边完全正常。

[PineL1eaf]

我学海八舍潘红臣实名签到

[Eaenlrg2]

试了一下用尾递归来解决斐波那契数列
···python
def fib_tail(n:int,a,b):
if n == 0:
return a
elif n == 1:
return b
return fib_tail(n-1,b,a+b)
fib_tail(10,0,1)
···

[Eaenlrg2]

def fib_tail(n:int,a,b):
    if n == 0:
        return a
    elif n == 1:
        return b     
    return fib_tail(n-1,b,a+b)
fib_tail(10,0,1)

之前的代码块有问题

[Wwh-SoEximious]

从这节开始明显变难了，想要理解得下功夫。我一年前被递归搞得遍体鳞伤，没想到一年后还是不咋样😂

[Mimi-ZQK]

可以看一下我的评论

[Mimi-ZQK]

分享一下【递归】这块我的学习心得，之前也在别的书上看过，看的时时候感觉懂了，事后不是忘了就是遇到具体问题时不会用，说明没有掌握其精髓，这里我已文中最开始的示例举另一种例子帮助新手理解，作者文中给的是1到5的等差数列相加，例子使用了一个recur(5)的函数来演示，该函数只有一个参数，设计的很巧妙，但新手可能不太好理解这种巧妙。这里我降低难度换另一种思路帮新手理解：要计算1到5的等差数列之和，我们很容易受到题目要求的影响，潜意识认为应该设计一个函数recur(a,b),并在实际调用时使用recur(1,5)的方式去调用，这种思路当然可以，我们就按这个思路去设计。递归讲究的是把复杂问题分解为简单问题来解决，所以我们要先利用这个思想，1+2+3+4+5我可能不会算，但1+2我会，2+3我会，3+4我也会，总之就是我会最简单的2个数相加，那就好办了，我们把1+2+3+4+5尽可能的简化为2个数相加的模式，然后我们通过观察会发现开始的第一步一定是1+2，最后一步是4+5，当然也可以反过来倒着算5+4+3+2+1,不论正算反算，最后都是2个数相加，并且两个数之间相差1（例如1+2种的1和2，以及4+5中的4和5），这样我们现在知道的中止递归的条件，那就是当两个数相减相差1的时候就是“递转归”的时机。于是有以下代码，该代码不仅可以计算1到5的等差数列之和，也可以计算其他类型等差数列之和，比如2到6，具体代码如下：

def recur(a, b):
    if b - a == 1:
        return a + b
    res = recur(a + 1, b)
    return res + a

c = recur(1, 5)
print(c)

最后我想对新手说的是，要想真正自己掌握递归，出了要记作者文中住递归用法的三个要素，更要自己动手去解一些递归小题目，不要一上来看答案，先尝试自己设计一下，会更容易让你理解递归！

[Mimi-ZQK]

第二种方法：

def recur(a, b):
    if b - a == 1:
        return a + b
    res = recur(a, b-1) + b
    return res

c = recur(1, 5)
print(c)

[net592]

谢谢您的邮件。我会尽快回复您！                                          

[wxl8]

def fib(n:int)->int:
res=0
if n==1 or n==2:
return n-1
res= fib(n-1)+fib(n-2)
print(f"number is {res}")
return res

print(fib(5))

number is 1
number is 2
number is 1
number is 3
3
有友友解释一下这个结果吗