Recursion to loop

Question

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.

You might now have a en.wikipedia.org/wiki/Primitive_recursive_function :) — Sash Sinha
– Sash Sinha, Commented Dec 6, 2016 at 2:43
Isn't the declaration of your problem wrong? Shouldn't the second line be T(0,m)=m, m>=0 instead? — Right leg
– Right leg, Commented Dec 6, 2016 at 2:49
@Rightleg Yeah, my bad. Edited it, thanks for pointing it out. — TheGroch
– TheGroch, Commented Dec 6, 2016 at 2:52

Paul Hankin · Accepted Answer · 2016-12-06 03:21:20Z

5

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

edited Dec 6, 2016 at 3:21

answered Dec 6, 2016 at 2:45

Paul Hankin

58.8k11 gold badges99 silver badges125 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

Jonathon Reinhart Over a year ago

Not that this solution requires C99 and allocates T on the stack, which may be too large for such an allocation, depending on n and m of course.

Paul Hankin Over a year ago

Yes it's C99 and potentially limited by stack. But n and m can't get too large anyway because the function grows exponentially and entries quickly overflow even a 64 bit int.

Paul Hankin Over a year ago

The code as written also assumes int has at least 24 bits ;)

TheGroch Over a year ago

That's a neat way to solve it and someone could use those ideas to theirs code. However, I forgot to add I'm supposed to be as basic as possible - no two-dimensional arrays, pointers etc. I should've been way more precisive when asking my question.

Paul Hankin Over a year ago

You can use a 1D array to represent the table: int T[(n+1) * (m+1)] with T[i][j] becoming T[i * (m+1) + j]. The code is otherwise essentially the same (only messier) and I'll leave it to you to finish your homework ;)

|

Collectives™ on Stack Overflow

Recursion to loop

1 Answer 1

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related