写递归的要点
明白一个函数的作用并相信它能完成这个任务,千万不要跳进这个函数里面企图探究更多细节, 否则就会陷入无穷的细节无法自拔,人脑能压几个栈啊。
—— OI-wiki
递归,就是一个函数自身调用自身。递归起到类似与循环的效果。但是,与循环不同,递归可以分支。如果循环一定是一条直线,那么递归可能是树形结构。
循环 -> 递归
前面说了,循环和递归很像。那么,我们可以将 for
循环尝试转为递归。先来一个循环的示例:
for(int i = 1; i <= n; i++)
{
printf("qwq, %d\n", n);
}
首先,让我们来想一想,for
循环的括号中 3 个语句分别是干什么的呢?
int i = 1;
这是循环的初始化,定义了一个变量 $i$,将其赋值为 $1$。i <= n;
这是循环每次进行下去的条件,当 $i>n$ 时即退出循环。i++
这是循环每次结束后干的事,当执行完循环体时, $i$ 则加 $1$。
这样回忆下来,可以发现,在 for
循环的括号中 3 个语句其实可以拆分出来。