Question

递归算法转为非递归

int fun(int m,int n)
{
int a,b,c;
if(n==1)
{
c = m;
}
else if(m==1)
{
c = n;
}
else
{
a = fun(m,n-1);
b = fun(m-1,n);
c = a+b;
}
return c;
}
大神们把我转一下吧

Answer 1

你自己维护一个存储空间就行了，我下面这个只是一个大体的思路，具体的细节还靠你自己去完善。
#define f(x,y) f[x*n+y]
int* f = malloc(m*n*sizeof(int));
for(i=0;i<m;++i)
f(0,i) = i;
for(j=0;j<n;++j)
f(j,0) = j;
for(i=1;i<m;++i)
for(j=1;j<b;++j)
f(i,j) = f(i-1,j)+f(i,j-1);
ret = f(m,n);
free f;
return ret;

Answer 2

int fun(int m,int n)
{
int i,j,c;
for(;m!=1;m--){}
for(;n!=1;n--){}
c = a+b;
return c;
}