рекурсии в цикл

Question

Я дано задание написания как повторяющиеся и итерации функции программы, которые определяются как:

Т (п, 0) = п, п> = 0
Т (0, т) = т, т> = 0
Т (п, т) = Т (п-1, м) + 2 * Т (п, м-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)); 
} 

Однако, делая это в итерации оказалось невозможным для меня. Я пытался это сделать довольно долго, я много читал об этом в Интернете - с очень небольшим успехом.
Каждый совет и вся помощь будут оценены.
Спасибо заранее!

Small edit: Забыл добавить, меня ограничивают большинство основных инструментов и возможностей языка 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; 
} 

Это позволяет оптимизировать код, чтобы использовать только 1D массив. Это работает, используя, по существу, тот же метод, что и 2D-версия, но осторожно и тонко использует элементы массива. Он использует более простые функции C, чем 2D-версия, но это, безусловно, не простой код, и мне лично это становится намного сложнее понять.

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]; 
}