递归学习笔记

本文同步发表在洛谷博客

我们充分发扬人类智慧：
将递推和递归混为一谈
在 \(dp\) 的基础上来学递归
然后把递推和 \(dp\) 混为一谈
然后我就发现：
™的我 \(dp\) 没学好！
然后去学 \(dp\)，
然后发现我递推没学好，
所以四舍五入我递归也学不好，
那就不学了！

好了让我们步入正题

正文

首先，递归recursive需要一个函数，我们叫这个函数rec：

int rec(int a){

}

void rec(int a){

}

然后我们拿洛谷的 P5739 计算阶乘 练练手：

P5739 计算阶乘

题目描述

求 \(n!\)，也就是 \(1\times2\times3\dots\times n\)。
挑战：尝试不使用循环语句（for、while）完成这个任务。

解题过程

暴力

在我们啥也不知道的时候，肯定是使用for循环暴力出奇迹：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,ans=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        ans*=i;
    }
    cout<<ans;
}
-----------------------
编程语言：C++20 O2

代码长度：160B

用时：16ms

内存：680KB

AC记录

动态规划，dp

首先，明白题目让我们做什么，显然是算出 \(1 \times 2 \times 3 \times ...... \times n-1 \times n\)

接着，确认第 \(i-1\) 步的状态是 \(1 \times 2 \times ...... \times i-1\)，第 \(i\) 步的状态是 \(1 \times 2 \times ...... \times i-1 \times i\)，因此，我们得出 dp 公式：

然后，我们可以写出以下代码：

#include<bits/stdc++.h>
using namespace std;
map<int,int>dp;
int main(){
    int n;
    cin>>n;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        dp[i]=dp[i-1]*i;
    }
    cout<<dp[n];
}
-------------------------------
编程语言：C++20 O2

代码长度：196B

用时：20ms

内存：564KB

怎么比暴力还慢？

AC记录

递归

这就是题面中说的挑战部分，以前我还不会做，现在会了。

根据上文我们提到的 dp 公式：