第六章递归

时间：2010-08-05 来源：静止的流水

求解递归程序有两种方法，一是直接求值，不需要回溯；二是不能直接求值的，需要回溯。前者转换为非递归程序，需要中间变量保存中间结果，成为直接转换法；后者需要用栈来保存中间结果，成为间接转换法。栈的设计，不能只拘泥于栈元素就是单个的一个值，可能是一个数组，比如stack[top][0]stack[top][1]stack[top][2]等等，用于保存不同的值。 1。直接转换法所有的迭代程序都可以转换为递归程序，但是并不是所有的递归程序都可以转换为迭代程序递归比迭代需要更多的时间和空间

int fabona(int n){
    if(n==1||n==2)
        return 1;
    else
        return fabona(n-1)+fabona(n-2);
}
int fabona2(int n){
    int s1 = 1;
    int s2 = 1;
    int s;
    for(int i = 1;i<n;i++){
        s = s1 + s2;
        s1 = s2;
        s2 = s;
    }
    return s;
}

2。间接转换法

需要用到栈来保存中间结果，一般流程如下：

初始状态入栈

while(栈不为空）{

栈顶元素S出栈；

if(s就是要找的结果）

else

计算s相关状态s1；

将s1入栈

}

typedef struct Node{
    char data;
    struct Node *left,*right;
}Node;
int counter(Node *t){
    if(t==NULL)
        return 0;
    else
        return counter(t->left)+counter(t->right)+1;
}
int counter2(Node *t){
    const int max(20);
    int count = 0;
    Node *stack[max],*node;
    int top = -1;
    top++;
    stack[top] = t;
    while(top>-1){
        count++;
        node = stack[top];
        top--;
        if(node->left!=NULL){
            top++;
            stack[top] = node->left;
        }
        if(node->right!=NULL){
            top++;