自动搬运

查看原文

来自洛谷，原作者为

	vegetable_king 全身全霊！MORE MORE JUMP!!

搬运于2025-08-24 21:07:42，当前版本为作者最后更新于2021-07-04 00:11:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在博客食用更佳。

本蒟蒻的第 $4$ 篇题解！

前置芝士（递归）

递归作为一种算法在程序设计语言中广泛应用， 基本含义是指函数、过程、子程序在运行过程序中直接或间接调用自身而产生的重入现象。——360百科

推荐一个讲递归比较清楚的博客

我并不认为递归像最上面说的那样麻烦，我认为递归就只是递归边界和函数调用的是罢了。

举个栗子：

int fib(int x){
	if (x < 3) return 1; // 递归边界
	return fib(x - 1) + fib(x - 2); // 函数递归调用

上面的函数，是求斐波那契数列第 $x$ 项的代码。

通过这个栗子，我们可以看出，递归边界是为了在特定情况下，防止函数再递归调用下去。上面，如果没有递归边界，这个函数就会继续调用，产生 $fib(0)$，$fib(-1)$ 等等奇怪的情况。而这一个递归边界，就是在函数无法再递归下去的时候（如果 $x<3$，$x-1$ 和 $x-2$ 其中一定会至少有一项 $<1$，也就是不合法）终止递归，返回斐波那契数列的第一项或第二项——$1$。

递归调用函数则是核心，每一个答案都是从其他的答案推导过来的。

如果我们往这个函数里传入一个参数 $5$，这个函数会发生像这样的事情：

$fib(5)$

$=fib(4)+fib(3)$

$=(fib(3)+fib(2))+(fib(2)+fib(1))$

$=((fib(2)+fib(1))+1)+(1+1)$

$=((1+1)+1)+2$

$=5$

每一项都是由前两项推导而成，这就是递归的一种简单的使用方法。

思路

这道题已经给你了所有的递归边界和递归调用方法，你只要把它转换成代码的形式，你就成功了！

代码

#include <bits/stdc++.h>
 
using namespace std;
 
int a, b;
int ack(int a, int b){
    if (a == 0) return b + 1;
    if (b == 0) return ack(a - 1, 1); // 递归边界
    return ack(a - 1, ack(a, b - 1)); // 函数递归调用
}
int main(){
    cin >> a >> b;
    cout << ack(a, b);
}