开发进行时...

递归设计：有程序出口；自己调用自己...

递归转非递归有两种方法
1、直接转换法
使用中间变量保存中间结果。
如费氏级数
f(1)=1
f(2)=1
f(n)=f(n-1)+f(n-2) n>2

递归

int Fib(int N)
{
    if(N<=1)
        return N;
    else
        return Fib(N-1) + Fib(N-2);
}

非递归

int Fib(int N)
{
    int i,s;
    s1=1; //s1 save f(n-1) 's value
    s2=1; //s2 save f(n-2) 's value
    s=1;
    for(i=3;i<=n;i++)
    {
        s=s1+s2;
        s2=s1;
        s1=s;
    }
    return s;
}

2、间接转换法
使用栈保存中间结果
将初始状态s0进栈
while(栈不为空)
{
退栈，将栈顶元素赋给s
if(s是要找的结果) 返回
else
{
寻找到s的相关状态s1
将s1进栈
}
}
如计算二叉树的所有结点个数
f(t)=0 若t=NULL
f(t)=1 若t->left=NULL且t->right=NULL
f(t)=f(t->left)+f(t->right)+1 基他

#递归

int counter(bitree *t)
{
    int num1,num2;
    if(t==NULL) return 0;
    else if(t->left==NULL && t->right==NULL) return 1;
    else
    {
        num1=counter(t->left);
        num2=counter(t->right);
        return num1+num2+1;
    }
}

非递归

#define n 100
typedef struct node
{
    char data;
    struct node *left, *right;
}bitree;

int counter(bitree *t)
{
    bitree *st[n], *p;
    int top, count=0;
    if(t != NULL)
    {
        top = 1;
        stack[top] = t; // push root node
        while(top > 0)
        {
            count++;    //node count ++
            node = stack[top]; //pop the root node
            top--;
            if(node->left != NULL)
            {
                top++;
                stack[top]=node->left;
            }
            if(node->right != NULL)
            {
                top++;
                stack[top]=node->right;
            }
        }
    }
    return count;
}