CODEWITHSUNDEEP
c++recursionsumiteration
Ganondalf
Ganondalf

Reputation: 73

How do I rewrite this recursively?

I wrote a sum of function code iteratively, I just want to redo it recursively. How do I do that? Without an invariant, I am a little lost.

The procedure, when given two integers, low and high, and a procedure for computing a function f, will compute f(low) + f(low + 1) + f(low + 2)+....+ f(high). For example, ( sumFunc(1, 9, square) == 285 )

int sumFunc(int low, int high, int f(int), int end) {
    if ( low == high)
        return f(low) + end;
    else 
        return sumFunc((low + 1), high, f(end + (f(low))));
}

int sum(int low, int high, int f(int)) {
    return sumFunc(low, high, f(int), 0);
}

Thank you!

Upvotes: 0

Views: 114

Answers (1)

WhozCraig
WhozCraig

Reputation: 66194

I think this is what you're after. This is the not-so-safe version that mandates the caller ensure low is no greater than high on invoke:

int sum(int low, int high, int f(int))
{
    return f(low) + ((low == high) ? 0 : sum(low+1, high, f));
}

If it is at-all-possible that low is ever greater than high on invoke, this needs a few safety checks to ensure you don't invoke overflow.

int sum(int low, int high, int f(int))
{
    if (low < high)
        return f(low) + sum(low+1, high, f);

    if (high < low)
        return f(high) + sum(high+1, low, f);

    return f(low);
}

Upvotes: 2

Related Questions