递归与循环比较

下面通过几个例子，对递归与循环进行比较。

递归1

#include<iostream>
using namespace std;
void dfs(int n)
{
   	if (n==0) return;
	   cout<<n<<” “;
　　dfs(n-1); 
}
int main()
{
	 dfs(10000);
    dfs(75000);//运行RE
}

　　说明递归对内存有一定的消耗

对应的循环

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n
    for (int i=n;i>0;i--) cout<<i<<" ";
    return 0;
}

　　输入

10000

75000均不会RE，因为不会产生内存消耗

递归2

#include<iostream>
using namespace std;
void dfs(int n)
{
    int a[10000]
	 if (n==0) return;
	 dfs(n-1); 
}
int main()
{
	dfs(75);//运行RE
	dfs(50);
}

　　说明递归对内存有一定的消耗，如果递归函数中有定义数组这种变量，内存消耗更大。对应循环

#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n
	for (int i=n;i>0;i--){ int a[10000]; cout<<i<<" ";}
	return 0;
}

　　输入

10000

75000均不会RE，因为不会产生内存消耗

递归3

#include<iostream>
using namespace std;
void dfs(int n)
{
	if (n==0) return;
	cout<<n<<" ";
	dfs(n-1);
	cout<<n<<" "; 
}
int main()
{
	dfs(5);
}

　　递归函数有递和归两个阶段

对应循环

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	for (int i=n;i>0;i--) {
		cout<<i<<" ";
	}
	for (int i=1;i<=n0;i++) {
		cout<<i<<" ";
	}
	return 0;
}

　　递归4

#include<iostream>
using namespace std;
void dfs(int n)
{
	if (n<=0) return;
	cout<<n<<" ";
	dfs(n-1);
	dfs(n-2);
}
int main()
{
	dfs(5);
}

　　输出5 4 3 2 1 1 2 1 3 2 1 1

这个递归用简单循环就比较难实现了，从递归树上理解其运行情况

递归5

#include<iostream>
using namespace std;
void dfs(int n)
{
	if (n<=0) return;
	cout<<n<<" ";
	dfs(n-1);
	cout<<n<<" ";
	dfs(n-2);
	cout<<n<<" ";
}
int main()
{
	dfs(5);
}

　　输出5 4 3 2 1 1 1 2 2 3 1 1 1 3 4 2 1 1 1 2 2 4 5 3 2 1 1 1 2 2 3 1 1 1 3 5

 递归6

#include<iostream>
using namespace std;
void dfs(int n)
{
	if (n<=0) return;
	cout<<n<<" ";
	dfs(n-1);
	cout<<n<<" ";
	dfs(n-2);
}
int main()
{
	dfs(5);
}

　　输出5 4 3 2 1 1 2 3 1 1 4 2 1 1 2 5 3 2 1 1 2 3 1 1

从递归树分析一下

递归可以实现多重循环且嵌套层次不是固定的，循环结构的循环嵌套格式，嵌套层次是固定的

递归7

#include<iostream>
using namespace std;
void dfs(int n)
{
	if (n<=0) return;
	for (int i=1;i<=n;i++)
	{
		cout<<i<<" ";
	}
	cout<<endl;
	dfs(n-1);
}
int main()
{
	dfs(2);
}

　　对应循环

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	for (int i=n;i>0;i--) {
		for (int j=1;j<=i;j++)
		{
			cout<<j<<" ";
		}
		cout<<endl;
	}
	return 0;
}

　　递归8

#include<iostream>
using namespace std;
void dfs(int n)
{
	if (n<=0) return;
	for (int i=1;i<=n;i++)
	{
		cout<<i<<" ";
		dfs(n-1);
	}
}
int main()
{
	dfs(3);
}

　　输出1 1 1 2 1 2 1 1 2 1 3 1 1 2 1

递归9

#include<iostream>
#include<vector>
using namespace std;
vector<int> p;
void dfs(int n)
{
	if (n<=0) 
	{
		for (int j=0;j<p.size();j++)
		{
			cout<<p[j]<<" ";
		}
		cout<<endl;
		return;	
	}
	for (int i=1;i<=n;i++)
	{
		p.push_back(i);
		dfs(n-1);
		p.pop_back();
	}
}
int main()
{
	dfs(3);
}

　　递归10

#include<iostream>
#include<vector>
using namespace std;
vector<int> p;
int N;
void dfs(int n)
{
	if (n<=0) 
	{
		for (int j=0;j<p.size();j++)
		{
			cout<<p[j]<<" ";
		}
		cout<<endl;
		return;	
	}
	for (int i=1;i<=N;i++)
	{
		p.push_back(i);
		dfs(n-1);
		p.pop_back();
	}
}
int main()
{
	N=2;
	dfs(N);
}