目录1. 简介2. 递推3. 递归3.1. 例题3.2. 练习题3.2. 辗转相除法实现4. 小结1. 简介递推与递归是算法中常见的思想。递推就是利用已经计算得的信息推算更多的信息并将这个过程循环进行直到计算出一系列所需信息。递归可以理解为函数自己调用自己来解决递推解决不了的问题。递推与递归是许多算法的基础是很重要的内容。2. 递推刚才提到的内容如果不理解可以看看下面这个例子给定正整数n nn求出∑ i 1 n i ! \sum_{i1}^n i!∑i1ni!其中! !!符号是阶乘对于所有m ≥ 1 , m ! m ⋅ ( m − 1 ) ⋅ ( m − 2 ) ⋅ . . . ⋅ 1 m\ge1,m!m\cdot(m-1)\cdot(m-2)\cdot...\cdot1m≥1,m!m⋅(m−1)⋅(m−2)⋅...⋅1特别地0 ! 1 0!10!1。答案对998244353 998244353998244353取模。数据范围1 ≤ n ≤ 10 6 1 \le n \le 10^61≤n≤106很明显这是让我们计算1 ∼ n 1\sim n1∼n的阶乘之和。它没有快速的求根公式因此我们需要通过递推的方式计算答案。我们知道n ! ( n − 1 ) ! × n n!(n-1)!\times nn!(n−1)!×n。如果我们已经知道( n − 1 ) ! (n-1)!(n−1)!就能快速求出n ! n!n!。因此我们使用一个循环从1 11到n nn分别计算并直接累加就能求出答案。代码#includebits/stdc.husingnamespacestd;constlonglongmod998244353;longlongsum,last1;// sum是答案last是上一个阶乘的值开始时last 0! 1intn;intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i){lastlast*i%mod;// 上一篇提到的取模方式sum(sumlast)%mod;}coutsum;}3. 递归有时简单的递推解决不了或很难解决某些问题特别是递归定义的函数值的计算。这个时候我们就要用到递归了。在数学中我们有通项公式和递推公式的区别。比如经典的斐波那契数列f ( 0 ) 1 , f ( 1 ) 1 , f ( x ) f ( x − 1 ) f ( x − 2 ) ( x ≥ 2 ) f(0)1,\ f(1)1,\ f(x)f(x-1)f(x-2)\ (x\ge2)f(0)1,f(1)1,f(x)f(x−1)f(x−2)(x≥2)这是它的递推公式。如果我们想要计算f ( 4 ) f(4)f(4)就要先算f ( 3 ) f(3)f(3)和f ( 2 ) f(2)f(2)。要算f ( 3 ) f(3)f(3)就要先算f ( 2 ) f(2)f(2)和f ( 1 ) f(1)f(1)。等等。但这个过程不会一直持续下去因为我们知道f ( 0 ) f(0)f(0)和f ( 1 ) f(1)f(1)的值而且括号里的x xx最终一定会跑到0 , 1 0,10,1中的一个就不需要再往下递归了。写成代码就是这样的intf(intx){if(x0||x1)return1;// 因为我们知道这两个值returnf(x-1)f(x-2);// 根据公式}这就是递归。其中if(x 0 || x 1) return 1;被我们称作终止条件。3.1. 例题我们看一道例题定义f ( x , y ) f ( x − 1 , y ) f ( x − 1 , y − 1 ) f(x,y)f(x-1,y)f(x-1,y-1)f(x,y)f(x−1,y)f(x−1,y−1)。当x 1 x1x1时f ( 1 , y ) y f(1,y)yf(1,y)y。当y 1 y1y1时f ( x , 1 ) 1 f(x,1)1f(x,1)1。给定x , y x,yx,y求f ( x , y ) f(x,y)f(x,y)。x ≤ 8 , y ≤ 8 x\le8,y\le8x≤8,y≤8。题意很简单注意好终止条件就行。代码intf(intx,inty){if(x1)returny;// 终止条件1if(y1)returnx;// 终止条件2returnf(x-1,y)f(x-1,y-1);}3.2. 练习题写代码计算以下函数f ( x ) f ( x − 1 ) × f ( x − 2 ) 1 , f ( 0 ) 1 , f ( 1 ) 2 f(x)f(x-1)\times f(x-2)1,\ f(0)1,\ f(1)2f(x)f(x−1)×f(x−2)1,f(0)1,f(1)2求f ( 6 ) f(6)f(6)。答案3411 34113411。f ( x ) 2 ∗ f ( x − 1 ) f ( x − 1 ) f ( x − 2 ) , f ( 0 ) 1 , f ( 1 ) 1 f(x)2*f(x-1)f(x-1)^{f(x-2)},\ f(0)1,\ f(1)1f(x)2∗f(x−1)f(x−1)f(x−2),f(0)1,f(1)1 求f ( 4 ) f(4)f(4)。 答案747 747747。3.2. 辗转相除法实现复习一下辗转相除法gcd ( a , b ) gcd ( b , a m o d b ) \gcd(a,b)\gcd(b,a \bmod b)gcd(a,b)gcd(b,amodb)当其中一项为0 00时另一项即为所求答案。intgcd(inta,intb){if(b0)returna;// 终止条件returngcd(b,a%b);// 递归式子}这里不需要保证a b a bab因为如果a b a bab递归一次之后就会变成gcd ( b , a ) \gcd(b,a)gcd(b,a)因为当a b abab时a m o d b a a \bmod b aamodba4. 小结今天我们学习了递归这个重要思想。它会在很多算法中出现请一定掌握。那么本段学习暂且就到这里我们下次再见。
