其实简单来说 ,能找出递推关系式的递归,也就是简单递归直接找出来进行。下面一个例子
/*求解阶乘
阶乘的定义就是 n!=n*(n-1)! 0!=1 1!=1*/
int Fact(int n)
{
if(n==0) return 1; //递归出口
return n*Fact(n-1) //n*Fact(n-1)就是递归式,其中n-1就是界函数
}
复杂的就可以就必须借用其他数据结构模型来完成,比如栈和队列。
下面给出快速排序递归和非递归的形式就是这个很好的例子。
快速排序非递归形式:
#include<stdio.h>
int partition(int a[],int l,int r){
int key=a[l],i=l,j=r;
while(i<j){
while(i<j && a[j] >= key)
j--;
if(i<j)
a[i++]=a[j];
while(i<j && a[i] <=key)
i++;
if(i<j)
a[j--]=a[i];
}
a[i]=key;
return i;
}
void qsort(int a[],int l,int r){
//boundary case
if(l>=r)
return;
//state 0
int mid=partition(a,l,r);
qsort(a,l,mid-1);
//state 1
qsort(a,mid+1,r);
//state 2
}
struct recorc{
int l,r,mid; //local virables. a[] never changed, no need to save.
int state;
}stack[100000];
void nun_recursive_qsort(int a[],int l,int r){
int state=0,top=0;
int mid;
while(1){
if(l>=r){ //boundary case, return previous level
if(top == 0)
break; //end of recursion
top--;
l=stack[top].l; //end of function, update to previous state
r=stack[top].r;
mid=stack[top].mid;
state=stack[top].state;
}else if(state == 0){
mid=partition(a,l,r);
stack[top].l=l; //recutsive call, push current state into stack
stack[top].r=r;
stack[top].mid=mid;
stack[top].state=1;
top++;
r=mid-1;
state=0; //don't forget to update state value
}else if(state == 1){
stack[top].l=l;
stack[top].r=r; //recursive call, push current state into stack
stack[top].mid=mid;
stack[top].state=2;
top++;
l=mid+1;
state=0;
}else if(state == 2){
if(top == 0)
break; //end of recursion
top--;
l=stack[top].l;
r=stack[top].r;
mid=stack[top].mid;
state=stack[top].state;
}
}
}
快速排序典型的递归形式:
template <class T>
void Quick(T *a, int left, int right) {
int i, j;
if (left < right)
{
do {
i = left;
j = right + 1;
do { i++; } while (a[i] < a[left]);
do { j--; } while (a[j] > a[left]);
if (i < j)
{
T temp = a[i];
a[i] = a[j];
a[j] = temp;
}
} while (i<j);
T temp = a[left];
a[left] = a[j];
a[j] = temp;
Quick(a, left, j - 1);
Quick(a, j + 1, right);
}
}
template <class T>
void QuickSort(T *p, int n)
{
Quick(p, 0, n - 1);
}
如果快速排序有疑问的参考: