Question

数据结构递归习题

将下面递归函数转换为等价的非递归函数。
(1) void P(int N)
{ if (N>0)
{ cout<<N; P(N-1); cout<<N;}
}

(2) void P(int N)
{ if (N>0)
{ P(N-1); cout<<N; P(N-1); }
}

(3) int f(int N)
{
if (N==0) return 0;
else if (N==1) return 1;
else return f(1)+f(2);
}

Answer 1

void P(int N)
{
    int i;
    for(i=N;i>0;i++)
        cout<<i;
}
void P(int N)
{
    int i;
    for(i=1;i<=N;i++)
        cout<<i;
    for(i=N;i>=1;i--)
        cout<<i;
}
int f(int N)
{
    int a[100],i;
    a[0]=0;
    a[1]=1;
    for(i=2;i<=N;i++)
       a[i]=a[i-1]+a[i-2];
    return a[N];
}