Lec 01 - Resursion 递归

递归的概念

递归是一种在计算机科学中非常重要的编程技术(思想), 它可以简化许多的问题

递归函数具体是指函数在定义的时候直接或者间接的调用自身的方式

举一个简单的递归程序 

1
2
3
4
5
6
7
8
9
10
#include <iostream>
using namespace std;

int main()
{
	cout << "zz" << endl;
	main(); // 在 main 函数的里面又调用了 main 函数, 这就是递归
	
	return 0;
}

(这个例子只是为了展示递归的思想, 不是为了解决真实的问题, 如果实际运行这个代码那么他会陷入死循环)

递归的概念

递归可以把一个大型的复杂的问题, 转化为一个与原问题相似, 但是规模较小的问题来求解. 直到子问题不能再被拆分, 可以直接求解, 递归就结束了. 递归的思考范式就是把大事化小的过程

递归中的递就是递推的意思, 归就是回归的意思, 接下来我们将慢慢体会

!–递归的必要条件–!

在书写递归的时候, 有两个必要条件:

  1. 退出: 递归存在限制条件, 当满足这个限制条件的时候, 递归💩不再继续
  2. 渐进: 在递归的过程中, 我们要不断的向着退出条件靠近

接下来我将举出几个例子让你体会体会…

例子1: n 的阶乘(factorial)

https://www.luogu.com.cn/problem/P5739

我们现在想要计算 n 的阶乘, 根据递归的思想, 大事化小… 想要计算 n 的阶乘, 就只要先把 n - 1 的阶乘计算出来, 再乘上 n, 就得到了 n 的阶乘

从 n 的阶乘公式不能看出: 如何把一个较大的问题, 转化为一个与原问题相似, 但是规模较小的问题来求解

n-1 的阶乘和 n 的阶乘是相似的问题, 但是规模较小, 其中有一钟特殊情况是: 当 n == 0的时候, n 的阶乘是 1. 而其余 n 的阶乘都是可以通过上面的公式计算的:

Pasted image 20260903112749

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int n;
int fact(int n)
{
    if (n == 0)
        return 1;
    return n * fact(n - 1);
}

int main()
{
    cin >> n;
    cout << fact(n);
    return 0;
}

(这里不考虑 n 太大的情况, n 太大存在栈溢出)

画图推演

Pasted image 20260903113802

递归与循环

求n的阶乘, 我们很容易就能得到递推公式, 但是这个问题也是可以用循环的方式去解决的.

想要计算 n 的阶乘, 只要能产生从 1~n 的数字, 然后累计相乘就好了

1
2
3
4
5
6
7
// 使用循环的方式实现
int fact2(int n)
{
    int res = 1;
    for (int i = 1; i <= n; i++) res *= i;
    return res;
}

说明:

这里简单的对比一下递归和循环的差异： 在C语言中每一次函数调用，都需要为本次函数调用在内存的栈区，申请一块内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者函数栈帧。

函数不返回，函数对应的栈帧空间就一直占用，所以如果函数调用中存在递归调用的话，每一次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。

所以如果采用函数递归的方式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起栈溢出(stack overflow)的问题。

所以就当前的问题来看，使用循环来解决更好，效率更高。

我们看到的许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更加清晰，但是这些问题的迭代实现往往比递归实现效率更高。当一个问题非常复杂，难以使用迭代的方式实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。

例子 2: 求第 n 个斐波那契数列

https://www.luogu.com.cn/problem/B2064

Pasted image 20260903121652 看到递推公式, 很容易诱导我们写成递归的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;

int fib(int a)
{
    if (a == 1 || a == 2) return 1;
    return fib(a - 1) + fib(a - 2);
}

int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int a; cin >> a;
        cout << fib(a) << endl;
    }
    return 0;
}

类似的, 我们会发现, 随着递归的深入, 冗余的计算变得越来越多. 其实对于斐波那契数列的计算使用递归的方式是非常不明智的, 我们可以采用迭代的方式去解决

你可以创建一个足够大的数组, 初始化好前两个元素为 1. 使用一个 for 循环计算, 往后的每一个元素都是前两个元素的和, 然后放到数组里面去. 这样的话进行一次初始化之后, 再进行查询的时间复杂度之间变为O(1)了

再者, 你也可以直接用递归的方式去计算第 n 个斐波那契数的结果, 在下面我给出一种实现方式

1
2
3
4
5
6
7
8
9
10
11
12
13
// 使用循环实现
int fib(int num)
{
    int a = 1, b = 1, c = 1;
    while (num > 2)
    {
        c = a + b;
        a = b;
        b = c;
        num--;
    }
    return c;
}

递归练习

练习1: 求 1+2+3+…+N 的值

https://www.luogu.com.cn/problem/B2142

练习 2: 阿克曼（Ackermann）函数

https://www.luogu.com.cn/problem/B2144

练习 3: digit 函数

https://www.luogu.com.cn/problem/B2145

练习 4: 求 f(x,n)

https://www.luogu.com.cn/problem/B2147

练习 5: 再求 f(x,n)

https://www.luogu.com.cn/problem/B2148

练习 6: 进制转换

https://www.luogu.com.cn/problem/B2143

我的解答

练习1: 求 1+2+3+…+N 的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// https://www.luogu.com.cn/problem/B2142
#include <iostream>
using namespace std;

int add(int n)
{
    if (n == 1) return 1;
    return n + add(n - 1);
}

int main()
{
    int n; cin >> n;
    cout << add(n) << endl;
    return 0;
}

练习 2: 阿克曼（Ackermann）函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;

int A(int m, int n)
{
    if (m == 0) return n + 1;
    else if (m > 0 && n == 0) return A(m - 1, 1);
    else return A(m - 1, A(m, n - 1));
}

int main()
{
    int m, n; cin >> m >> n;
    cout << A(m, n) << endl;
    return 0;
}

练习 3: digit 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;

int digit(int n, int k)
{
    if (k == 1) return n % 10;
    return digit(n / 10, k - 1);
}

int main()
{
    int n, k; cin >> n >> k;
    cout << digit(n, k) << endl;
    return 0;
}

练习 4: 求 f(x,n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include  <cmath>
using namespace std;

double f(double x, int n)
{
    if (n == 1) return sqrt(1 + x);
    return sqrt(n + f(x, n - 1));

}

int main()
{
    double x; int n;
    cin >> x >> n;
    printf("%.2lf", f(x, n));
    return 0;
}

练习 5: 再求 f(x,n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

double f(double x, int n)
{
    if (n == 1) return x / (x + 1);
    return x / (n + f(x, n - 1));
}


int main()
{
    double x; int n;
    cin >> x >> n;
    printf("%.2lf", f(x, n));
    return 0;
}

练习 6: 进制转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <string>
using namespace std;

string a = "0123456789ABCDEF";

string cvs(int x, int m)
{
    if (x < m) return to_string(x);
    return cvs(x / m, m) + a[x % m];
}

int main()
{
    int x, m; cin >> x >> m;
    cout << cvs(x, m) << endl;
    return 0;
}