c - 递归循环

Question

我的任务是编写函数的循环程序和迭代程序，定义为:

T(n,0)=n, n>=0
T(0,m)=m, m>=0
T(n,m)=T(n-1,m)+2*T(n, m-1)

我只能使用基本操作(例如 +、-、*、/、%)，不允许使用任何库中的大多数“外部”函数。 为此编写递归并不是什么大问题(代码在 C 中):

int fTrec(int n, int m)
{  
    if(n==0)
        return m;
    else if(m==0)
        return n;
    else
        return(fTrec(n-1, m)+2*fTrec(n, m-1));
}

然而，对我来说，让它进入迭代是不可能的。我已经尝试完成它很长一段时间了，我已经在互联网上阅读了很多关于它的内容 - 但收效甚微。
我们将不胜感激每一个提示和所有帮助。
提前致谢!

小编辑:忘了补充，我仅限于C语言的最基本工具和可能性。我的意思是仅使用一维数组，不使用指针等。

Answer 1

您可以通过构建结果表来迭代计算函数。这非常符合制作计算递归公式的动态规划解决方案的精神。

下面是一些示例代码:

#include <stdio.h>

int fTiter(int n, int m) {  
    int T[n+1][m+1];
    for (int i = 0; i <= n; i++) {
        T[i][0] = i;
    }
    for (int i = 0; i <= m; i++) {
        T[0][i] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            T[i][j] = T[i-1][j] + 2 * T[i][j-1];
        }
    }
    return T[n][m];
}

int main(int argc, char *argv[]) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            printf("% 8d ", fTiter(j, i));
        }
        printf("\n");
    }
    return 0;
}

可以优化代码以仅使用一维数组。这使用与 2D 版本基本相同的方法工作，但以谨慎和微妙的方式重用数组元素。它使用比 2D 版本更简单的 C 功能，但它绝对不是更简单的代码，我个人觉得它更难理解。

int fTiter(int n, int m) {  
    int T[n+1];
    for (int i = 0; i <= n; i++) {
        T[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        T[0] = i;
        for (int j = 1; j <= n; j++) {
            T[j] = T[j-1] + 2 * T[j];
        }
    }
    return T[n];
}