递归与迭代

简介: <p>1、递归</p> <p>当函数用自身来定义时就称为是递归(recursive)的。</p> <p>递归必须满足四个基本法则:</p> <p>(1)、基本情形:必须给出基准情况,不用递归就能求出,用于终止递归运算;</p> <p>(2)、不断推进:对于那些要被递归求解的情形,递归调用必须能够朝着一个基准情形推进;</p> <p>(3)、设计法则:假设所有的递归调用都能运行;<

1、递归

当函数用自身来定义时就称为是递归(recursive)的。

递归必须满足四个基本法则:

(1)、基本情形:必须给出基准情况,不用递归就能求出,用于终止递归运算;

(2)、不断推进:对于那些要被递归求解的情形,递归调用必须能够朝着一个基准情形推进;

(3)、设计法则:假设所有的递归调用都能运行;

(4)、合成效益法则:在求解一个问题的同一个实例时,切勿在不同的递归调用中做重复性的工作。


2、迭代

迭代就是利用变量的原值推算出变量的一个新值。

若递归是自己调用自己的话,迭代就是自己不停的调用别人。


3、实例一

求解:阶乘n!之和,即:


示例代码如下:

#include<iostream>
using namespace std;

float fun(int m)
{
	
	float mm=1;
	for(int i=1;i<=m;i++)	//迭代
	{
		mm *= i;
	}
	if(m==0)
		return 1;	//base case(基准情况)
	else
		return fun(m-1)+(1/mm);	//递归
	
}

 int main()
 {
	int n;
	cout<<"请输入n:";
	scanf("%d",&n);
	cout<<fun(n)<<endl;;
	
 }


4、实例二

求解:有n个台阶,如果一次只能上1个或2个台阶,求一共有多少种上法?

解析:如果只有一级台阶,n=1,很明显只有一种跳法;如果有两级台阶,n=2,则有两种跳法,一种是跳两下1级,一种是直接跳两级;

那么我们来看看如果有n层台阶,可以怎么跳:

n层台阶可以是这么够成的:

(1)、第n层台阶是从第n-1层跳1级上来的

(2)、第n层台阶是从第n-2层直接跳2级上来的

所以可以得到n层的跳法总数是F(n)=F(n-1)+F(n-2)

#include <iostream>
using namespace std;

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

int main()
{
	int n;
	printf("请输入台阶总数n:");
	scanf("%d",&n);
	cout<<"共有"<<Solve(n)<<"种跳法"<<endl;
	return 0;
}

5、实例三

求解:用递归的方法判断一个数组是否为递增数组

基本思想:记录当前最大的,并且判断当前的是否比这个还大,大则继续,否则返回false结束。

#include<iostream>
using namespace std;

bool fun(int a[], int n)
{
	if(n==1)
		return true;
	if(n==2)
		return a[n-1]>a[n-2];

	return fun(a,n-1) && ( a[n-1]>a[n-2] );
}

int main()
{
	int a[]={0,1,2,3,4,5,6,7,8,9};
	int n=sizeof(a)/sizeof(int);
	cout<<fun(a,n)<<endl;
}



目录
相关文章
|
7月前
二叉树的统一迭代遍历法
二叉树的统一迭代遍历法
37 0
|
2月前
6.2二叉树的迭代遍历
6.2二叉树的迭代遍历
29 1
|
2月前
|
存储
使用迭代代替递归
使用迭代代替递归
|
2月前
|
算法
递归和迭代详解
递归和迭代详解
02_二叉树的迭代遍历
02_二叉树的迭代遍历
|
4月前
|
算法
【算法】递归总结:循环与递归的区别?递归与深搜的关系?
【算法】递归总结:循环与递归的区别?递归与深搜的关系?
|
算法
用递归的思想实现二叉树前、中、后序迭代遍历
用递归的思想实现二叉树前、中、后序迭代遍历
70 1
|
7月前
|
算法
递归算法和迭代算法有什么不同
递归算法和迭代算法有什么不同
66 1
二叉树的遍历(递归And迭代)
二叉树的遍历(递归And迭代)
49 0
|
缓存 算法 Java
使用迭代优化递归程序
大家好,我是王有志。 今天我们将会分析上篇文章中递归算法存在的问题,并通过迭代去优化。
114 1
使用迭代优化递归程序