计算概论与程序设计基础_函数的递归_

程序设计中的递归算法递归算法是程序设计中一种重要的编程思想和技巧。

它通过自身调用来解决问题，使得问题可以分解为更小的子问题，并逐步求解这些子问题，最终得到原问题的解。

在程序设计中，递归算法常常用于处理具有递归性质的问题，解决这些问题时可以简化代码结构，提高代码的可读性和可维护性。

下面将介绍递归算法的定义、特点以及应用领域。

一、递归算法的定义递归算法是指一个函数或过程在其定义中直接或间接地调用自身的算法。

递归算法通过将原问题转化为规模较小的相同问题来求解，直到问题规模缩小到可以直接解决的程度，最后将子问题的解合并为原问题的解。

二、递归算法的特点1. 自相似性：递归算法在问题的求解过程中，使用相同的方法来处理子问题。

原问题的求解方法和子问题的求解方法是一致的，它们之间只在问题规模上存在差异。

2. 递归调用：递归算法通过函数或过程的自身调用来解决问题。

在每一次递归调用中，问题规模都会减小，直到问题规模缩小到可以直接解决的程度。

3. 终止条件：递归算法必须有一个终止条件，当满足终止条件时，递归停止，不再进行调用。

否则，递归将陷入无限循环。

三、递归算法的应用领域递归算法在程序设计中应用广泛，以下是几个常见的应用领域：1. 数学计算：递归算法可以用于解决数学问题，如斐波那契数列、阶乘等。

例如，斐波那契数列可以使用递归算法来求解，其定义如下：```fib(n) = fib(n-1) + fib(n-2)，其中n >= 2。

fib(0) = 0，fib(1) = 1。

```2. 数据结构：递归算法在数据结构中的应用非常广泛，如二叉树的遍历、图的深度优先搜索等。

以二叉树的中序遍历为例，其递归算法实现如下：```void inorderTraversal(TreeNode* root) {if (root == nullptr) {return;}inorderTraversal(root->left);cout << root->val << " ";inorderTraversal(root->right);}```3. 字符串处理：递归算法可以用于解决字符串处理的问题，如字符串反转、括号匹配等。

【C】函数递归算法讲解在数学与计算机科学中，递归算法是指在函数的定义中使用函数自身的方法。

在程序中，递归是通过函数的调用来实现的。

函数直接调用其自身，称为直接递归；函数间接调用其自身，称为间接递归。

在函数定义中，其内部操作又直接或间接地调用了自身，则称这样的函数为递归函数。

生活中我们也存在这样的递归现象，比如：从前有座山,山里有个庙，庙里有个老和尚和一个小和尚。

一天，老和尚在对小和尚讲故事，故事的内容是：从前有座山,山里有个庙，庙里有个老和尚和一个小和尚。

一天，老和尚在对小和尚讲故事，故事的内容是：从前有座山,山里有个庙，庙里有个老和尚和一个小和尚。

一天，老和尚在对小和尚讲故事，故事的内容是……故事中又调用了这个故事正如函数中又调用了这个函数一样。

•••••••••••#include<iostream>using namespace std;int f()//自定义函数{ return f();}int main()//主函数 { cout<<f();//函数调用 return 0;} 但上述函数的定义是不合理的，因为递归函数和生活中的递归现象具有不同之处：生活中有些递归现象可以无限递归，但递归函数必须有递归终止条件。

所以，递归函数有两大要素：①递归关系式：对问题进行递归形式的描述。

②递归终止条件：当满足该条件时以一种特殊情况处理而不是用递归关系式处理。

参考程序：••••••••••••••••••#include<iostream>using namespace std;void output(int n)//自定义函数 { if(n==1) cout<<1<<' ';//递归终止条件 else//递归关系式 { output(n-1); cout<<n<<' '; } }int main()//主函数{ int n; cin>>n; output(n);//函数调用 return 0;}参考程序：•••••••••••••#include<iostream>using namespace std;int sum(int n)//自定义函数 { if(n==1) return 1;//递归终止条件 else return n+sum(n-1);//递归关系式}int main()//主函数{ int n; cin>>n; cout<<sum(n);//函数调用 return 0;}参考程序：•••••••••••••#include<iostream>using namespace std;int jc(int n)//自定义函数 { if(n==1) return 1;//递归终止条件 else return n*jc(n-1);//递归关系式 }int main()//主函数 { int n; cin>>n; cout<<jc(n);//函数调用 return 0;}参考程序：••••••••••••••#include<iostream>using namespace std;int xn(int x,int n)//自定义函数 { if(n==0) return 1;//递归终止条件 else return x*xn(x,n-1);//递归关系式}int main()//主函数{ int x,n; cin>>x>>n; cout<<xn(x,n);//函数调用 return 0;}参考程序：•••••••••••••#include<iostream>using namespace std;int f(int n)//自定义函数 { if(n<=1) return n;//递归终止条件 else return f(n-1)+f(n-2);//递归关系式 }int main()//主函数 { int n; cin>>n; for(int i=0;i<=n;i++) cout<<f(i)<<' ';//函数调用 return 0;}••••••••••••••#include<iostream>using namespace std;int gcd(int m,int n)//自定义函数 { if(m%n==0) return n;//递归终止条件 else returngcd(n,m%n);//递归关系式}int main()//主函数{ int m,n; cin>>m>>n; cout<<gcd(m,n);//函数调用 return 0;}••••••••••••••••••••••••••#include<iostream>using namespace std;int a[20];bool flag;//利用全局变量falg传递结果void judge(int n,int m)//自定义函数{ if(a[n]==m) flag=true;//递归终止条件else if (n==1) return;//递归终止条件 else//递归关系式 { judge(n-1,m-a[n]); judge(n-1,m); }}int main()//主函数 { int n,m; cin>>n; for (int i=1; i<=n; ++i) cin>>a[i]; cin>>m; flag=false; judge(n,m);//函数调用if (flag) cout<<'YES'<<endl; else cout<<'NO'<<endl; return 0;}••••••••••••••••••••••••#include<iostream>#include<cmath>using namespace std;int sum;void res(int a,int y)//自定义函数{ for(int i=y;i<=sqrt(a);i++) { if(a%i==0) res(a/i,i); } sum++;}int main()//主函数{ int n,a; cin>>n; while(n--) { cin>>a; sum=0; res(a,2); cout<<sum<<endl; } return 0;}••••••••••••••#include<iostream>using namespace std;int f(int n)//自定义函数 { if(n==1) return 1;//递归终止条件 else return 2*f(n-1)+1;//递归关系式}int main()//主函数 { int n; cin>>n; cout<<f(n);//函数调用 return 0;}•••••••••••••••••••#include<iostream>using namespace std;int step=0;//步数void hanoi(int n,char a,char b,char c)//自定义函数{ if(n==1) cout<<'第'<<++step<<'步：'<<'将圆盘'<<n<<'从'<<a<<'移动到'<<c<<endl; else { hanoi(n-1,a,c,b); cout<<'第'<<++step<<'步：'<<'将圆盘'<<n<<'从'<<a<<'移动到'<<c<<endl; hanoi(n-1,b,a,c); } }int main()//主函数 { int n; cin>>n; hanoi(n,'A','B','C');//函数调用 return 0;}。

递归函数什么是递归函数？在编程中，递归函数是一种直接或间接地调用自身的函数。

递归在很多算法和数据结构中都有广泛的应用，它能够简化问题的解决步骤并提高代码的可读性。

使用递归函数时，我们只需要关注当前步骤的解决方式，而不需要关心前面步骤的细节。

递归的基本原理递归函数的基本原理是将一个大问题划分为一个或多个相似的小问题，并通过解决这些小问题来解决整个大问题。

递归函数的定义通常包含两个部分： 1. 基线条件：当问题达到基线条件时，递归将停止。

这是递归函数的出口，也是递归函数中没有再次调用自身的终止点。

2. 递归条件：当问题未达到基线条件时，递归函数将调用自身来处理子问题。

递归函数的示例下面我们通过一些示例来说明递归函数的使用方法。

示例一：计算阶乘def factorial(n):if n ==0:return1else:return n * factorial(n-1)在这个示例中，我们定义了一个递归函数factorial()，它用于计算一个非负整数的阶乘。

如果输入参数n的值为0，则函数返回1；否则，函数返回n乘以factorial(n-1)的结果。

通过逐步调用factorial()函数，我们最终可以得到所需的阶乘值。

示例二：计算斐波那契数列def fibonacci(n):if n <=1:return nelse:return fibonacci(n-1) + fibonacci(n-2)斐波那契数列是一个经典的递归问题。

在上面的示例中，我们定义了一个递归函数fibonacci()，它用于计算斐波那契数列中第n个数的值。

如果n的值小于等于1，则直接返回n；否则，返回fibonacci(n-1)和fibonacci(n-2)的和。

通过逐步调用fibonacci()函数，我们可以得到斐波那契数列中任意位置的数值。

递归函数的优缺点递归函数有以下几个优点： 1. 递归函数可以简化问题的解决步骤，使代码更加简洁易懂。

函数递归的概念函数递归是指函数在定义中调用了自身的一种特殊形式。

递归可以在解决问题中提供一种更简洁、优雅的方法，因为它允许将问题分解成更小的、类似的子问题。

递归函数通常具有基本情况和递归情况。

在函数递归中，基本情况是指无需再次调用自身的情况。

递归情况是指函数需要再次调用自身以解决较小子问题的情况。

通过每次调用函数自身并向基本情况靠近，最终可以解决原始问题。

为了更好地理解函数递归的概念，我们可以通过一个简单的例子来说明。

考虑计算阶乘的函数。

阶乘是指将一个非负整数n 与所有小于等于n 的正整数相乘的结果。

在函数中，阶乘可以用递归的方式来计算。

首先，我们需要定义函数的基本情况。

在这种情况下，当n 等于0 或1 时，阶乘的结果是1，因为0 和1 的阶乘都是1。

接下来，我们定义递归情况。

在此示例中，阶乘的递归情况是当n 大于1 时，阶乘的结果是n 乘以(n-1) 的阶乘。

使用这个递归定义，我们可以编写一个计算阶乘的函数。

在函数中，我们首先检查基本情况，如果n 等于0 或1，则直接返回1。

否则，我们将调用函数本身来计算(n-1) 的阶乘，并将结果乘以n，最终得到n 的阶乘。

这个过程会不断重复，直到达到基本情况。

下面是一个使用递归来计算阶乘的Python 代码示例：def factorial(n):if n == 0 or n == 1:return 1else:return n * factorial(n-1)使用这个函数，我们可以计算任意正整数的阶乘。

例如，计算5 的阶乘可以通过调用`factorial(5)` 来实现。

函数递归不仅可以用于解决简单问题，也可以用于解决更复杂的问题。

递归的关键是将大问题划分为更小的可解决子问题。

通过调用函数本身，可以不断地解决这些子问题，最终达到解决原始问题的目的。

然而，值得注意的是，函数递归可能会导致性能上的问题。

每次递归调用都会生成一个新的函数栈帧，而函数栈帧的调用和返回会占用内存和额外的时间。

函数的递归函数的递归是一种重要的编程技术，它可以帮助我们解决很多复杂的问题。

在本篇文档中，我将介绍什么是函数的递归，为什么使用递归，如何使用递归以及递归的一些注意事项。

什么是函数的递归？在编程中，函数的递归是指一个函数调用自己的过程。

换句话说，递归是指将问题分解成较小的、更易解决的子问题，并且通过递归调用函数来解决这些子问题，最终将所有子问题组合在一起得到问题的解。

为什么使用递归？递归的一个优点是它可以让我们解决一些非常复杂的问题。

在递归中，我们可以将一个复杂的问题转化成一系列相对简单的问题，而这些简单问题又可以通过递归进行解决。

递归也可以使代码更加简洁和整洁。

当我们使用递归时，代码中通常会出现相同的模式，而这些模式可以被归纳为递归函数。

这减少了代码的复杂性，并使代码更易于维护。

如何使用递归？当我们使用递归时，我们需要考虑以下几个方面：1. 定义递归基递归基是指问题的最小规模的子问题。

例如，如果我们要计算一个数字的阶乘，那么递归基就是当数字为 1 时，阶乘就是 1。

在递归函数中，我们需要考虑什么时候到达递归基的情况，以及如何处理这种情况。

2. 缩小问题的规模在递归函数中，我们需要将问题分解成较小的子问题。

例如，如果我们要计算一个数字的阶乘，我们可以将问题分解成计算该数字减 1 的阶乘的问题。

3. 组合解在递归函数中，我们需要将子问题的解组合在一起得到问题的解。

例如，如果我们要计算一个数字的阶乘，我们可以将数字乘以计算出的一个较小数字的阶乘。

下面是一个计算阶乘的递归函数的示例：``` def factorial(n): if n == 1: # 递归基return 1 else: return n * factorial(n - 1) # 缩小问题的规模和组合解 ```在这个函数中，当 n 为 1 时，我们已经到达了递归基。

否则，我们将问题缩小到计算 n - 1 的阶乘，并将 n 与 n - 1 的阶乘相乘来组合解。