第六章递归

求解递归程序有两种方法，一是直接求值，不需要回溯；二是不能直接求值的，需要回溯。前者转换为非递归程序，需要中间变量保存中间结果，成为直接转换法；后者需要用栈来保存中间结果，成为间接转换法。

栈的设计，不能只拘泥于栈元素就是单个的一个值，可能是一个数组，比如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++;