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

[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)

[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
有友友解释一下这个结果吗

[majiang213]

def fib(n: int, count: int):
    count += 1
    print(f"n = {n} count {count}")
    if n == 1 or n == 2:
        return n - 1, count
    n1, c1 = fib(n - 1, count)
    n2, c2 = fib(n - 2, c1)
    print(f"n1 = {n1} n2 = {n2} sum = {n1 + n2}")
    return n1 + n2, c2

n1, c1 = fib(5, 0)

print(f"n = {n1} count {c1}")

你可以试着运行这个代码

n = 5 count 1
n = 4 count 2
n = 3 count 3
n = 2 count 4
n = 1 count 5
n1 = 1 n2 = 0 sum = 1
n = 2 count 6
n1 = 1 n2 = 1 sum = 2
n = 3 count 7
n = 2 count 8
n = 1 count 9
n1 = 1 n2 = 0 sum = 1
n1 = 2 n2 = 1 sum = 3
n = 3 count 9

[majiang213]

看看是不是好理解点

[ZZY080]

这个其实就属于迭代,迭代的好处在于不会有栈溢出，对于有的递归可以进行记忆优化达到和迭代类似的效率

[TianMaker]

算了一下好像是因为这个递归树是后序遍历输出的原因，你可以算一下这个二叉树后序遍历，正好是f(3),f(4),f(3),f(5),对应1，2，1，3。但我也是小白不知道是不是这个原因

[wkz2003]

3.嵌套循环里的c代码strncat(res, tmp, size - strlen(res) - 1);，参数"size - strlen(res) - 1"是不是传错了

[akiradavidsong]

斐波那契数列上面的代码有点难懂，改成我这个就容易理解一些
def fib(n):
if n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)

[rui-project]

对的，对的，我也是这么写的。效率应该比博主给的高一些，尾递归+递归树

[ffmm520]

你这样写还是有问题的，n == 1 的时候，返回值应该是 0，而不是 1。

而且不存在效率更高的说法。针对文中的写法，第一个 if 如果满足，程序就 return 结束了。不满足自然会走到下面的 return，所以第一个 if 中的 return 其实就暗含了一个 else 代码块在后面，最终执行结果和你用 if else 一样。

更多这种写法可以搜索“谓语句”

[sahiwhdssda23]

这样写n == 1的时候就不对了吧

[ZKey-7]

如果归的部分是这样 return function(x-1) * x; 这算尾递归吗？return function(x-1) * 5这样呢

[majiang213]

这两种都不算尾递归

[aludean]

我一直觉得尾递归这个名字很具有迷惑性，我说一下我看了一些博客对尾递归的理解。
首先递归这个概念应该分为形式上和计算上。

• 形式上：自己调用自己就叫递归。
• 计算上：有递和归两个过程，递是调用自己的过程，归是收缩并计算结果的过程。所谓“自上而下”地解决问题就在于递设置好计算链条以及计算链条中的数值的占位，归的收缩把数值填入并计算。

尾递归在形式上是自我调用，但是在计算上是迭代，一步一步完成计算，归的过程只是返回结果。

[ZZY080]

解释的很棒

[xinzihe]

这里开始，就要认真琢磨了；可能需要看很久才可以理清楚

[Dennis-1202]

我是不是太蠢了，自学了一轮python的基础代码之后来看这里感觉有点束手无策，自己着手复现出来代码也感觉有点困难

[ffmm520]

浅谈一下尾递归和普通递归的区别

前置知识：

• 以下均以 Java 代码为例
• Java 方法的入栈、出栈流程，局部变量的存储位置

先说结论：主要区别就是看递归调用后，是否还有局部变量参与计算。

/* 普通递归 */
int recur(int n) {
    // 终止条件
    if (n == 1)
        return 1;
    // 递：递归调用
    int res = recur(n - 1);
    // 归：返回结果
    return n + res;
    // ↑↑↑↑↑↑↑以上为原文中代码，下面的为修改后的代码
    // 上面两行代码和以下代码效果相同，
    // return n + recur(n - 1);
}

先看上面普通递归的代码，在执行了递归方法后，生成了一个局部变量 res, 同时方法参数 n 也为局部变量。因为需要局部变量参与运算，所以方法不能弹栈，得保存栈帧信息，才能让递归方法在返回后拿到局部变量做进一步计算，即原文中的“上下文”。

将原文中的最后两行代码改为 return n + recur(n - 1); 后，能更直观的能看到局部变量 n 在递归返回后参与了计算，若不持有上一个方法的“上下文”，如何拿到 n 的值？

/* 尾递归 */
int tailRecur(int n, int res) {
    // 终止条件
    if (n == 0)
        return res;
    // 尾递归调用
    return tailRecur(n - 1, res + n);
}

再看尾递归的代码， 在 return tailRecur(n - 1, res + n) 一行能看到递归方法调用后，不需要局部变量参与计算了，因为 n - 1 和 res + n 会先计算出实际的值，再将真实的值传给下一个递归方法。而下一个递归方法拿到值后直接做相关的计算，用不到上一个递归方法的变量。此时上一个递归方法相对于下一个递归方法来说已经“无用”了，即不需要持有上一个递归方法的“上下文”，此时编译器/虚拟机可针对此种情况做优化，将上一个递归方法弹栈，以节省内存空间。

[ZZY080]

说的很到位简洁明了

[yucuitai]

速速上去

[xiaomayisjh]

小白问一嘴，为啥什么不在递归的时候使用一个列表储存前面的函数结果最后直接相加呢，这样就可以及时释放内存了

[beihuxiansheng]

当然可以，加了存储就是动态规划解法，动态规划的递归解法就是递归加存储

[OrangeAlien]

如果递归函数返回类型是 void ，算不算尾递归

[liuyang1858]

/* 尾递归 /
int tailRecur(int n, int res) {
// 终止条件
if (n == 0)
return res;
// 尾递归调用
return tailRecur(n - 1, res + n);
}
函数的运算发生在形参内部，最后一步操作是调用自身。
/ 递归 */
int recurII(int n) {
// 终止条件
if (n == 1)
return 1;
return recurII(n-1)+n;
}
函数先调用自身进行计算，虽然是最后一步返回操作，返回的是调用自身后的计算值。

更直接的方法就是看有没有直接参与运算。

不知道理解对不对。

[lastVigo]

javascript的运行环境也没有做尾递归优化，小心爆栈。

[yrrlxhj]

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