CODEWITHSUNDEEP
crecursioniteration
TheGroch
TheGroch

Reputation: 33

Recursion to loop

I've been given an assignment of writing both recurring and iterating programs of function, defined as:

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

I am allowed to use only basic operations (so +, -, *, /, %) and not allowed to use most of "outside" functions from any libraries. Writing recursion for that wasn't that much of a problem (code is in 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));
}

However, making it into iteration turned out to be impossible for me. I've been trying to get it done for quite a while now, I've read quite a lot about it on internet - with very little success.
Every tip and all the help will be appreciated.
Thanks in advance!

Small edit: Forgot to add, I am limited to most basic tools and possibilites of C language. By this I mean using only one dimensional arrays, no pointers etc.

Upvotes: 3

Views: 85

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58201

You can compute the function iteratively by building up a table of results. This is very much in the spirit of making a dynamic programming solution that computes a recursive formula.

Here's some example code:

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

It's possible to optimise the code to use a 1D array only. This works using essentially the same method as the 2D version, but reuses elements of the array in a careful and subtle way. It uses simpler C features than the 2D version but it's definitely not simpler code, and I personally find it a lot harder to understand.

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

Upvotes: 5

Related Questions