第二讲 递归与递推剖析

算法总结之递推与递归递推算法递归算法⼤致包括两⽅⾯的内容：1）递归起点； 2）递归关系递推起点递归起点⼀般由题⽬或者实际情况确定，不由递归关系推出。

如果⽆法确定递归起点，那么递归算法就⽆法实现。

可见，递归起点是递归算法中的重要⼀笔。

递推关系递归关系是递归算法的核⼼。

常见的递归关系有以下⼏项：1）⼀阶递推；2）多阶递推；3）间接递推；4）逆向递推；5）多维递推。

下⾯通过栗⼦来详细介绍⼀下上述类别的递推关系。

1. ⼀阶递推在计算f(i)时，只⽤到前⾯项中的⼀项，如等差数列。

公差为3的等差数列，其递推关系为：f(i)=f(i-1)+3eg. 平⾯上10条直线最多能把平⾯分成⼏部分？分析：以直线数⽬为递推变量，假定i条直线把平⾯最多分成f(i)部分，则f(i-1)表⽰i-1条直线把平⾯分成的最多部分。

在i-1条直线的平⾯上增加直线i，易得i与平⾯上已经存在了的i-1条直线最多各有⼀个交点，即直线i最多被分成i段，⽽这i段将会依次将平⾯⼀分为⼆，即直线i将最多使平⾯多增加i部分。

所以，递推关系可表⽰为：f(i)=f(i-1)+i易得当0条直线时，平⾯为1部分。

所以f(0)=1为递推起点。

上述分析可⽤下⾯代码表⽰（c++）：#define MAX 100int f[MAX] //存放f（i）int lines(int n){//输⼊n为直线数⽬//输出最多部分数int i;f(0)=1;for(i=1;i<=n;i++){f[i]=f[i-1]+3;}return f[i];}2. 多阶递推在计算f(i)时，要⽤到前⾯计算过的多项，如Fibonacci数列。

eg.求Fibonacci的第10项。

分析：总所周知，Fibonacci数列中的第n项等于第n-1项加上n-2项。

所以递推关系为f(i)=f(i-1)+f(i-2);且f[0]=f[1]=1。

C++代码如下：#define MAX 100int f[MAX];int fib(int n){//输⼊n为项数//输出第n个fib数int i;f[0]=0;f[1]=1;for(i=2;i<=n;i++){f[i]=f[i-1]+f[i-2];}return f[n]}3. 间接递推在计算f[i]时需要中间量，⽽计算中间量要⽤到之前计算过的项。

数列的递推关系与递归公式数列是数学中常见的概念，指的是一系列按照特定规律排列的数字或者数值。

在数学的研究中，人们常常需要研究数列的性质和规律，以便进一步应用于数学问题的解决或者其他相关领域的研究中。

数列的递推关系和递归公式是研究数列的重要方法和工具，在本文中，我们将对数列的递推关系和递归公式进行详细的解析和探讨。

一、递推关系数列的递推关系是指数列中的每一项与它前面的一项或多项之间的关系。

通过递推关系，我们可以通过已知的数列元素求解未知的数列元素，从而揭示出数列中的规律和性质。

递推关系有多种形式，下面以几个具体的例子来说明。

例一：斐波那契数列斐波那契数列是一种经典的数列，它的递推关系可以用如下的公式表示：Fn = Fn-1 + Fn-2，其中F0=0，F1=1。

也就是说，斐波那契数列中的每一项等于它前面两项的和。

比如，数列的前几项为0、1、1、2、3、5、8...，可以通过递推关系求得。

例二：等差数列在等差数列中，每一项与它前面的一项之间的差值相等。

递推关系可以用如下的公式表示：an = an-1 + d，其中d是公差。

比如，数列的前几项为1、3、5、7、9...，可以通过递推关系求得。

例三：等比数列在等比数列中，每一项与它前面的一项之间的比值相等。

递推关系可以用如下的公式表示：an = an-1 * r，其中r是公比。

比如，数列的前几项为2、4、8、16、32...，可以通过递推关系求得。

通过以上的例子，我们可以看出，递推关系可以帮助我们找到数列中每一项之间的规律和关系，进而求解未知的数列元素。

二、递归公式递归公式是一种通过数列前面的多项元素来求解后面元素的公式。

递归公式在数列的研究中起到重要的作用，它可以帮助我们建立数列的数学模型并进行进一步的分析。

以斐波那契数列为例，递归公式可以表示为：Fn = F(n-1) + F(n-2)，其中n为数列的序号（从0开始），F0=0，F1=1。

递归公式是一种通过数列的前面两项来求解后面的项，不断地利用递归公式可以求得数列中的任意一项。

递归递推区别分析与例题总结递归与递推⽂章⽬录特点递归(recursive)运⾏过程中⾃我调⽤，求解过程分为回溯和递推两个过程，占⽤内存多（栈数先积累后收缩，有可能爆栈），代码简洁但低效。

尾递归和递归区别⬇function story() {从前有座⼭，⼭上有座庙，庙⾥有个⽼和尚，⼀天⽼和尚对⼩和尚讲故事：story() // 尾递归，进⼊下⼀个函数不再需要上⼀个函数的环境了，得出结果以后直接返回。

}function story() {从前有座⼭，⼭上有座庙，庙⾥有个⽼和尚，⼀天⽼和尚对⼩和尚讲故事：story()，⼩和尚听了，找了块⾖腐撞死了 // ⾮尾递归，下⼀个函数结束以后此函数还有后续，所以必须保存本⾝的环境以供处理返回值。

}尾递归省内存、⾼效(相当于（或者说递推？）)Python⽆法在语⾔中实现尾递归优化(Tail Call Optimization, TCO)，所以采⽤了for, while等特殊结构代替recursive的表述（优化是编译器⼲的，发现尾递归结构就给优化了）。

递推(iterative)效率⽐递归⾼，尽量递推，除⾮只能递归。

例题递推例⼦⼀般都是数学题。

重点是找递推公式（也太好偷懒了吧）平⾯分割问题直线分割平⾯（基本结论）如果当前有 n 条直线，新增加⼀条直线（第 n+1 条直线），可以多出来 n 个交点（新的直线和之前所有的直线都有交点），⽽多出来 n 个交点对应到可以多出 n+1 个平⾯（⽐如从两条线，⼜新增⼀条线时，新的线和两条线都相交，作⽤在三个区域上，对这三个区域切分，增加三个平⾯）。

也即：S n+1=S n+(n+1)=1+(n+1)(n+2)2当平⾯上已有n-1条曲线将平⾯分割成a n-1个区域后，第n-1条曲线每与曲线相交⼀次，就会增加⼀个区域，因为平⾯上已有了n-1条封闭曲线，且第n条曲线与已有的每⼀条闭曲线恰好相交于两点，且不会与任两条曲线交于同⼀点，故平⾯上⼀共增加2(n-1)个区域，加上已有的a n-1个区域，⼀共有a n-1+2(n-1)个区域。

递推与递归三、递推法递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。

设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。

能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为i的解。

这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。

【问题】阶乘计算问题描述：编写程序，对给定的n（n≦100），计算并输出k的阶乘k！（k=1，2，…，n）的全部有效数字。

由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整数数组的每个元素只存储长整数的一位数字。

如有m位整数N用数组a[ ]存储：N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100并用a[0]存储长整数N的位数m，即a[0]=m。

按上述约定，数组的每个元素存储k的阶乘k！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素……。

例如，5！=120，在数组中的存储形式为：3 0 2 1 ……首元素3表示长整数是一个3位数，接着是低位到高位依次是0、2、1，表示成整数120。

计算阶乘k！可采用对已求得的阶乘(k-1)！连续累加k-1次后求得。

例如，已知4！=24，计算5！，可对原来的24累加4次24后得到120。

细节见以下程序。

# include <stdio.h># include <stdlib.h># define MAXN 1000void pnext(int a[ ],int k){int *b,m=a[0], i, j, r ,carry;b=(int * ) malloc(sizeof(int)* (m+1));for ( i=1;i<=m;i++) b[i]=a[i];for ( j=1;j<=k;j++){for ( carry=0,i=1;i<=m;i++){r=a[i]+b[i]+carry;a[i]=r%10;carry=r/10;}if (carry) a[++m]=carry;}free(b);a[0]=m;}void write(int *a,int k){ int i;printf(“%4d！=”,k);for (i=a[0];i>0;i--)printf(“%d”,a[i]);printf(“\n\n”);}void main(){int a[MAXN],n,k;printf(“Enter the number n: “);scanf(“%d”,&n);a[0]=1;a[1]=1;write(a,1);for (k=2;k<=n;k++){pnext(a,k);write(a,k);getchar();}}四、递归递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，为此在进一步介绍其他算法设计方法之前先讨论它。

离散数学中的递归与递推知识点区分递归和递推作为离散数学中的重要概念，常常被混淆使用。

虽然两者都涉及到数列或函数的定义和计算，但它们在思想和方法上存在一些明显区别。

本文将从定义、特点和应用等方面对递归和递推进行深入探讨，以期帮助读者准确理解并运用两者。

一、递归的基本概念和特点递归是指在数学中，一个定义中出现对所定义对象本身的描述。

简而言之，就是一个问题的解能够通过不断地调用相同问题的解来进行求解。

举一个简单的例子，阶乘的递归定义如下：n！ = n * (n-1)！从上述定义可以看出，阶乘的计算通过不断地调用相同问题的解来进行求解。

递归具有以下几个基本特点：1. 终止条件：递归定义中必须包含一个或多个终止条件，以避免无限递归的发生。

在阶乘的例子中，当n等于0或1时，阶乘的值已经确定，不需要再进行递归调用。

2. 自相似性：递归定义中的每一步都与问题本身具有相同的性质，即通过不断缩小问题的规模来求解。

在上述阶乘的例子中，每一步的计算都与整个阶乘的计算过程相同，只是问题规模减少了。

3. 递归调用：在递归中，问题的解不断地通过调用相同问题的解来获得。

在阶乘的例子中，计算n的阶乘需要先计算(n-1)的阶乘。

二、递推的基本概念和特点递推是指通过已知的初始条件和规则，根据已知的项计算后续的项。

递推是用迭代的方式进行计算，其中每一步的计算仅依赖于之前的计算结果。

举一个简单的例子，斐波那契数列的递推定义如下：F(n) = F(n-1) + F(n-2)，其中F(0) = 0， F(1) = 1递推具有以下几个基本特点：1. 初始条件：递推定义中必须包含一个或多个初始条件，以确定计算的起点。

在斐波那契数列的例子中，初始条件是F(0)和F(1)的取值。

2. 依赖关系：递推定义中每一项的计算都依赖于之前的计算结果。

在斐波那契数列的例子中，要计算第n项，需要先计算第n-1项和第n-2项。

3. 迭代计算：递推通过迭代计算的方式来求解问题，每一步都可以通过已知的计算结果得到下一步的计算结果。

递归与递推递推递归递归：从已知问题的结果出发，⽤迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为递归。

递推：从已知道的若⼲项出发，利⽤递推关系依次推算出后⾯的未知项的⽅法，我们称为递推算法。

递推与递归不同：递归是从未知到已知逐步接近解决问题的过程，⽽递推从已知到未知。

递推算法是⼀种⽤若⼲步可重复运算来描述复杂问题的⽅法。

递推是序列计算中的⼀种常⽤算法。

通常是通过计算前⾯的⼀些项来得出序列中的指定项的值。

递推的关系式可以暴枚找规律，也可以化繁为简，例如铺砖问题，最后⼀列砖铺与不铺，以及最后两列砖铺与不铺的情况相加即可求出关系式。

⽽关于递归，就是函数中再次调取函数，从⽽使困难的问题化为“1+1”类型简单的问题，得出结果再还原，操作过程类似于“U”型。

递归的重点是找到递归关系和递归出⼝。

……（概念太多，直接摆题）经典例题统计奇数和偶数个3内存限制：128 MiB时间限制：1000 ms标准输⼊输出题⽬类型：传统评测⽅式：⽂本⽐较题⽬描述在所有的N位正整数中，有多少个数中有偶数个数字3？⼜有多少个数有奇数个3？由于结果可能很⼤，你只需要输出这个答案对12345取余的值。

输⼊格式输⼊⼀个数N(1<=N<=1000)，输⼊形式为⽂件输⼊，以读到0或⽂件末尾结束。

输出格式对于每⼀个N位正整数，输出有多少偶数个3以及多少奇数个3，中间⽤空格隔开。

样例样例输⼊2样例输出73 17数据范围与提⽰分别找出奇数偶数的递推式样例说明：在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个对于⼀位数，除3外，其他全为含有偶数个三（数组元素初始化），紧接着，对于两位数，13，23，30~39（除33外）【这⾥有9个数，也可以进⾏思考】，43，53，63，73，83，93含有奇数个三，再看三位数（差不多就可以找到规律……）。

声明：a数组存储含奇数个三的个数，b数组⽤于存储偶数i的数值 1 2 3 ……a[i] 1 17 674 ……b[i] 8 73 226 ……So,a[i]=(b[i-1]+a[i-1]*9)%12345,b[i]=(a[i-1]+b[i-1]*9)%12345;#include<cstdio>using namespace std;int main(){int n,a[10005],b[10005];a[1]=1,b[1]=8;for(int i=2;i<=1001;i++){a[i]=(b[i-1]+a[i-1]*9)%12345;b[i]=(a[i-1]+b[i-1]*9)%12345;}while(scanf("%d",&n)!=EOF){if(n==0)return 0;printf("%d %d\n",b[n],a[n]);}return 0;}Hanoi塔内存限制：128 MiB时间限制：1000 ms标准输⼊输出题⽬类型：传统评测⽅式：⽂本⽐较题⽬描述问题的提出：Hanoi塔由n个⼤⼩不同的圆盘和三根⽊柱a,b,c组成。

递归与递推公式的掌握技巧掌握递归与递推公式的技巧在计算机科学领域中，递归和递推公式是重要的概念和工具。

递归是指在一个函数或过程内部调用自己，直到满足某个条件才返回结果。

递推公式是指通过前面的结果推导出后面的结果的公式，也称为递归公式。

递归和递推公式在算法设计、数据结构、数学等领域都得到了广泛应用。

递归和递推公式的掌握是编程和数学学习的重点之一。

在实际应用中，掌握递归和递推公式对程序的正确性、效率和可读性都是至关重要的。

本文将介绍如何掌握递归和递推公式的技巧，帮助读者更好地应用它们解决问题。

第一部分：递归的设计和实现递归的设计和实现是一项重要的技巧。

递归函数的设计和实现需要考虑以下几个方面：1.确定递归的终止条件递归的过程必须能够终止，否则会造成死循环或栈溢出等问题。

因此，在设计递归函数时必须确定递归的终止条件。

例如，计算斐波那契数列的递归函数可以定义如下：```int fibonacci(int n) {if (n <= 1) {return n;}else {return fibonacci(n - 1) + fibonacci(n - 2);}}```在这个例子中，当n小于或等于1时，递归终止，返回n的值。

如果n大于1时，递归调用fibonacci函数求解f(n-1)和f(n-2)的和。

递归终止条件的确定是函数正确实现的关键之一。

2.转化问题的规模递归通常是为了解决类似于“分而治之”的问题。

通过递归调用将原问题拆分成子问题，并在子问题得到解后合并得到原问题的解。

例如，快速排序算法就是一种递归的排序算法，它的实现如下：```void quick_sort(int arr[], int left, int right) {if (left < right) {int pivot = partition(arr, left, right);quick_sort(arr, left, pivot - 1);quick_sort(arr, pivot + 1, right);}}int partition(int arr[], int left, int right) {int pivot = arr[right];int i = left - 1;for (int j = left; j < right; j++) {if (arr[j] <= pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[right]);return i + 1;}```在这个例子中，快速排序通过递归调用将原问题拆分为更小的子问题，并在子问题解决后进行合并。

在数学中，递归关系与递推公式是两个常常使用的概念。

它们用于描述数列、函数或者其他数学对象之间的关系，并且在数学问题的解决中起到了重要的作用。

在本文中，我们将详细讲述递归关系和递推公式的概念、性质以及应用。

首先，我们来看递归关系。

递归关系通常用于定义一个数列或者函数，它通过将问题分解为更小的子问题来进行定义。

具体来说，一个递归关系由两部分组成：初始条件和递归步骤。

初始条件是一个或一组已知的数值，用于开始递归过程。

递归步骤则描述了如何从已知的值推导出后续的值。

递归过程在每一步都会使用之前的值来计算新的值，直到得到所需的结果为止。

举一个简单的例子来说明递归关系。

考虑斐波那契数列，它定义如下：第一个数字为0，第二个数字为1，从第三个数字开始，每个数字都是前两个数字的和。

用递归关系来定义斐波那契数列可以写成：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2）。

我们可以看出，这个递归关系将问题分解为计算前面两个数字的和，这样就可以得到后续的数字。

递归关系的另一个重要应用是在数学归纳法的证明中。

数学归纳法是一种证明思想，用于证明一般情况下的命题。

它主要分为两个步骤：基础步骤和归纳步骤。

基础步骤是证明命题在某个特定情况下成立，而归纳步骤则是假设命题在某个情况下成立，然后通过递归关系证明在下一个情况下也成立。

递归关系在归纳步骤中起到了至关重要的作用，它提供了从一个情况到下一个情况的连接。

与递归关系相对应的是递推公式。

递推公式是一种通过前面的值计算出后续的值的公式。

它不需要进行递归的计算，而是直接使用已知的值进行计算。

递推公式在解决一些数学问题时具有很大的便利性，因为它们可以快速得到所需的结果。

递推公式与递归关系有着密切的联系。

事实上，递推公式可以从递归关系中推导出来，而递归关系也可以通过递推公式来表示。

它们在描述数学对象之间的关系时起到了互补的作用。

最后，我们来看一些常见的应用。

递归关系和递推公式广泛应用于数列、函数、动态规划等数学问题的解决中。

递归算法和递推算法的原理-概述说明以及解释1.引言1.1 概述递归算法和递推算法是编程中常用的两种算法思想，它们都是一种问题解决的方法论。

递归算法通过将一个大问题分解为一个或多个相同的小问题来解决，而递推算法则是通过给定初始条件，通过逐步推导出后续结果来解决问题。

递归算法是一种自调用的算法，它将一个问题划分为更小规模的相同子问题，并通过调用自身来解决这些子问题。

每个子问题的解决方案被合并以形成原始问题的解决方案。

递归算法具有简洁的代码结构和易于理解的逻辑。

它在一些问题上能够提供高效的解决方案，例如树的遍历、图的搜索等。

递推算法则是从已知的初始条件开始，通过根据给定的递推公式或规则，逐步计算出后续的结果。

递推算法是一种迭代的过程，每一次迭代都会根据已知条件计算得出下一个结果。

递推算法常应用于数学问题，求解斐波那契数列、阶乘等等。

递归算法和递推算法在解决问题时的思路不同，但也存在一些相似之处。

它们都能够将大问题分解成小问题，并通过解决这些子问题来获得问题的解决方案。

而且递归算法和递推算法都有各自适用的场景和优缺点。

本文将详细介绍递归算法和递推算法的原理、应用场景以及它们的优缺点。

通过比较和分析两者的差异，帮助读者理解和选择合适的算法思想来解决问题。

1.2文章结构文章结构部分的内容可以描述文章的整体框架和各个章节的内容概要。

根据给出的目录，可以编写如下内容：文章结构：本文主要探讨递归算法和递推算法的原理及其应用场景，并对两者进行比较和结论。

文章分为四个部分，下面将对各章节的内容进行概要介绍。

第一部分：引言在引言部分，我们将对递归算法和递推算法进行简要概述，并介绍本文的结构和目的。

进一步，我们将总结递归算法和递推算法在实际问题中的应用和重要性。

第二部分：递归算法的原理在第二部分，我们将详细讨论递归算法的原理。

首先，我们会给出递归的定义和特点，探索递归的本质以及递归算法的基本原理。

其次，我们将展示递归算法在不同的应用场景中的灵活性和效果。