当前位置:C++技术网 > 资讯 > 数据结构笔记分享:40 递归转换非递归

数据结构笔记分享:40 递归转换非递归

更新时间:2016-02-04 20:07:56浏览次数:1+次

其实简单来说 ,能找出递推关系式的递归,也就是简单递归直接找出来进行。下面一个例子

/*求解阶乘
阶乘的定义就是 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);
}
如果快速排序有疑问的参考:

分治算法简单介绍(实战快速排序)