Ackmann函数 题解

· · 题解

在博客食用更佳。

本蒟蒻的第 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);
}