第 6 集 · B1 · 7 分钟
C 语言 · 第6集 · 递归：萝卜和套娃
从 Hello World、循环、递归讲到汉诺塔和动态规划，句子短，适合跟读。 开头：任务，或者说一类算法，
中俄字幕
задач, ну или класс алгоритмов,
任务，或者说一类算法，
при этом в процессе решения возникает подзадача или подзадачи, постановка которых
在解决过程中会产生一个或多个子任务，其定义方式
аналогична постановке исходной задачи.
与原始任务的定义类似。
что это значит?
这是什么意思？
Ну, ярким выражением является фраза: " чтобы понять рекурсию, надо понять рекурсию".
一个典型的说法是：“要理解递归，就必须先理解递归。”
Но правда, это бесконечная рекурсия, а у нормальной рекурсии должен быть конец.
但事实上，这是无限递归；而正常的递归必须有终止条件。
Давайте посмотрим на примере.
我们来看一个例子。
посадил дед репку.
老爷爷种了一棵萝卜。
Что значит посадил дед репку?
“老爷爷种了一棵萝卜”是什么意思？
Это значит, что репка ставит некоторую задачу.
这意味着萝卜提出了某个任务。
Давайте эту задачу конкретизируем.
让我们具体化这个任务。
Допустим, чтобы вытащить репку, требуется 200 ньютонов.
假设拔出萝卜需要200牛顿的力。
это требование необходимо, чтобы вытащить трепку.
这是拔出萝卜所必需的条件。
Ну, это аналогично примерно весу 20 килограмм.
这大约相当于20公斤物体的重量。
Соответственно, дед тянет, потянет, да, но у деда сил хватит только на.
因此，爷爷用力拉、再拉，是的，但爷爷的力气只有……
100 ньютонов. Соответственно, что получается?
100牛顿。那么结果如何？
Что репка ставит задачу деду.
萝卜给爷爷布置了一个任务。
Понимаете? То есть от репки идет задание деду.
明白吗？也就是说，任务是从萝卜发出给爷爷的。
Выдай мне, пожалуйста.
请给我……
выдай мне, пожалуйста, 200 ньютонов.
请给我200牛顿。
Понятно, да? 200 ньютонов- это задание.
明白了吗？200牛顿——这是任务目标。
а у деда всего, у самого деда,
而爷爷呢，就只有……爷爷本人呢，
да, у него всего лишь 100 ньютонов.
对，他仅有100牛顿的力气。
значит ему не хватает до того чтобы вытянуть репку
所以他拉不出萝卜，还差多少力？
ему не хватает еще 100 ньютонов он ставит задачу он ставит задачу бабке он зовет
他还差100牛顿，于是他把任务交给奶奶，叫她来帮忙。
бабку позвал дед бабку
爷爷叫来了奶奶。
Итак, что у нас бабка?
那么，奶奶的情况如何？
Какая у нее сила?
她的力气有多大？
Ей поставлена задача выдать 100 Ньютонов, но имеет бабка силы всего лишь 50
她被要求提供100牛顿的力，但她自己仅有50牛顿的力气。
Ньютонов. она как дед тянуть не может.
牛顿。她和爷爷一样，也拉不动。
Соответственно, бабка ставит задачу, как известно, внучке, да?
因此，奶奶把任务交给了孙女，对吧？
Внучка за бабку.
孙女替奶奶出力。
Значит, бабка ставит задачу внучке.
也就是说，奶奶把任务交给了孙女。
Она говорит: " Внучка дорогая, надо выдать".
她说：“亲爱的孙女，得把它拉出来。”
50 ньютонов. Внучка молодец.
50牛顿。孙女真棒！
внучка молодец, она обладает силой в 30 ньютонов.
孙女真棒，她能施加30牛顿的力。
но, конечно, не бабка.
但当然，不是奶奶。
Тянут, потянут, вытянуть не могут.
拉呀，拽呀，就是拉不出来。
Почему? Потому что внучка не может решить свою задачу без вызова вспомогательного
为什么？因为孙女无法在不调用辅助算法的情况下解决自己的问题。
алгоритма. Алгоритм точно такой же: тянуть.
这个算法完全一样：拉。
Позвала внучка жучку.
孙女叫来了小虫子。
жучки внучка тоже ставит задачи, то есть это вызов, call, да, то есть мы вызываем
小虫子也给孙女布置任务，也就是说这是一种调用（call），对，我们就是在调用。
каждого зверя, да, как функцию.
相应地，我们依次调用每只动物，对，就像调用函数一样。
Соответственно, у меня вот этот вызов.
因此，我这里就是这个调用。
Предлагается жучке дать 20 ньютонов.
要求小虫子提供20牛顿的力。
Но у жучки есть сила всего лишь в 10 ньютонов.
但小虫子只有10牛顿的力。
Соответственно, 10 ньютонов остаётся для кого?
那么，剩下的10牛顿该给谁呢？
Ну, как известно, позвала жучка кошку.
众所周知，小虫子叫来了猫。
окошка за ручку.
窗户拉着小手。
Значит, кошка.
所以，是猫。
Итак. зовем кошку.
那么，我们叫猫来。
У кошки задача выдать недостающие жучке 10 ньютонов.
猫的任务是给甲虫提供缺失的10牛顿力。
То есть, сейчас я поясню еще один важный момент, 10 ньютонов выдает, должна выдать
也就是说，我现在再说明一个关键点：这10牛顿力必须由猫来提供。
кошка. Но у кошки, к сожалению, нашлось только 9 ньютонов.
但遗憾的是，猫只找到了9牛顿力。
Вот, она не может решить данную ей задачу.
看，它无法完成分配给它的任务。
И она решает свою задачу с помощью вспомогательной задачи, а именно зовёт кошка
于是，它通过一个辅助任务来解决自己的问题，也就是猫去叫老鼠。
мышку. зовет кошка мышку.
猫叫老鼠。
Соответственно, что у нас получается?
那么，我们得到了什么结果？
Она ставит ей задачу дать усилие в 1 ньютон.
它给老鼠布置了一个提供1牛顿力的任务。
Ну, это примерно.
嗯，大致如此。
сколько это? вес 100 грамм, да?
这是多少？重量是100克，对吗？
ну если это у нас 10 килограмм, да, это у нас килограмм, значит, ну это вот 100
嗯，如果这是10千克，那这个就是1千克，所以这个就是100
грамм, значит, надо выдать.
克，所以得发出去。
И чем замечательна эта мышка?
这只老鼠有什么特别之处？
Мышка замечательна тем, что она решает свою задачу.
这只老鼠的特别之处在于它能独立完成自己的任务。
Абсолютно самостоятельно.
完全独立。
Если бы эта сказка продолжилась, да, позвала мышка
如果这个童话继续下去，嗯，老鼠就叫来了
мушку, да, мушка комара, комар клопа, клоп микроба, да, микроб и так далее, то у нас
小飞虫，嗯，小飞虫叫来了蚊子，蚊子叫来了臭虫，臭虫叫来了微生物，嗯，微生物等等，那么我们就会
получилась бы бесконечная рекурсия, то есть эта сказка, она б не имела конца, да,
出现无限递归，也就是说，这个童话将永无止境，嗯，就是这样。
вот это вот. Но, к счастью, вот этого всего нет.
但幸运的是，这一切并不存在。
у нас мышка является супергероем да я даже не знаю как выделить я не знаю желтеньким
我们的老鼠是超级英雄。天啊，我甚至不知道该怎么高亮——我不知道用黄色。
ее кружочком обведу вот так вот супергерой мышка почему
我用圆圈把它圈起来，就这样——超级英雄老鼠，为什么呢？
мы назовём её крайний случай.
我们叫她‘ крайний случай’（极端情况）吧。
Мышка у нас крайний случай, крайний, то есть она стоит с краю.
我们的老鼠就是‘ крайний случай’（极端情况）——‘ крайний’意思是她站在最边上。
а все остальные герои этой сказки решают свою задачу рекуррентно.
而这个童话中其余所有角色都递归地解决自己的任务。
ну кроме репки репка здесь вообще постановщик задачи она к рекурсии напрямую не
嗯，除了萝卜——萝卜完全是问题的发起者，它本身并不直接参与递归。
относится то есть рекурсия начинается вон там.
也就是说，递归是从那里开始的。
давайте вернемся еще раз каждый из них решая свою задачу вызывал другую функцию
我们再回顾一下：他们每个人都通过调用另一个函数来解决自己的任务。
каждая функция вызывала другую функцию и задача решалась в результате рекуррентно но
每个函数都调用另一个函数，最终任务通过递归方式得到解决，但……
обратите внимание они вызывают, да, то есть дед вызывает бабку, да, а бабка должна
请注意，他们是相互调用的，对吧？比如爷爷调用奶奶，对吧？而奶奶则必须……
сообщить ему усилие, но усилие вернется к нему не сразу, как он позвал.
告诉他需要施加的力，但这个力不会在他呼喊后立即返回。
Деду нужно, чтобы были выданы полностью 100 ньютонов.
爷爷需要完全施加100牛顿的力。
Поэтому реальное решение задачи, ну кроме того, что дед перед
因此，问题的实际解法——嗯，除了爷爷在……之前，
тем, как на самом деле использовать бабку, он же сообразил, что именно бабку, что
真正使用奶奶之前，他意识到，恰恰该找奶奶，
попросить у нее нужно именно 100 ньютонов, да, так вот,
向她请求的力值恰好是100牛顿，对，就是这样，
реальное решение задачи, да, оно начинается на самом деле с конца.
问题的实际解法，对，其实是从结尾开始的。
От крайнего случая разворачивается сюда.
即从极端情况反向推演到这里。
То есть с помощью мышки кошка может выдать свои 10 ньютонов, да, требуемые точнее,
也就是说，借助鼠标，猫可以施加它自己的10牛顿力，更准确地说，是所需的力。
да. С помощью кошки, да, с помощью кошки жучка может выдать уже 20 ньютонов, а не
对。借助猫，对，借助猫，小虫就能施加20牛顿的力，而不是
10. И так далее.
10牛顿。以此类推。
То есть получается, что у меня есть прямой ход рекурсии, да, когда идут вызовы.
也就是说，我有一个递归的正向过程，是的，就是函数调用发生的时候。
прямой ход рекурсии.
递归的正向过程。
И есть обратный ход, когда возвращаются результаты.
还有一个反向过程，即结果返回的时候。
И обратный ход, он естественно идет в обратном направлении.
反向过程自然是以相反的方向进行的。
обратный ход рекурсии то есть когда у нас по сути стек вызовов на
递归的反向过程，也就是当我们的调用栈在……
прямом ходу он увеличивается увеличивается адреса возврат
正向过程中，调用栈不断增长，返回地址也不断增长。
来源：Тимофей Хирьянов · CC BY 3.0