Why is Counting Down Considered Less Work in Recursive Functions?

[JimmyK]

In class, we're learning about recursive functions. One example given was figuring out 1 + 2 + 3+ 4 + 5 + 6 + 7 + 8 + 9 + 10. My professor stated to address this, we start with 10 in the function and decrement for the next recursive call, so 10 + f(9). He said going the other way would be considered more work, 1 + f(2), and a recursive function should do the least amount of work possible. I don't get why this is considered more work. It would be the same number of steps either way. What's the benefit of counting down instead of up in terms of the workload? Thanks.

 

[Xitami]

http://ideone.com/4q4wC

 

[MisterX]

There's no benefit to adding from right to left rather than left to right, assuming the "work" to add two numbers is always the same.

Xitami, there are issues with the code you posted.

Anyway here is code that demonstrates it should take the same number of recursive steps, and arrive at the same result.

http://ideone.com/MFJth

 

[rcgldr]

The overhead is the same for a fixed input, but the decrementing function is more flexible since the max value is specified as an input instead of a define or global variable.

#include <stdio.h>

static int ld, lu, i;

int fd(n){
    ld++;
    if(n>0)return n+fd(n-1);
    return 0;}
 
int fu(n){
    lu++;
    if(n<i)return n+fu(n+1);
    return i;} 
 
int main(){
    ld = lu = 0;
    for(i = 0; i <= 10; i++){
        printf("%d ",fd(i));
        printf("%d ",fu(0));}
    printf("\n%d %d\n", lu, ld);
    return(0);}

output:

0 0 1 1 3 3 6 6 10 10 15 15 21 21 28 28 36 36 45 45 55 55 
66 66

 

[MisterX]

retracted

 

[rcgldr]

using a for loop to do iterative addition when the topic is about finding a sum with recursion & using recursive incrementation to implement addition.

Unless someone deleted a post, none of the posts in this thread include an example of summation via a for loop. The for loop in my post was used to invoke the recursive summation routines 11 times, to run the summation for 0->0 to 0->10 cases. The incrementing done in the recursive functions was done to compare the overhead (how many times each function was called), the 11 cases resulted in a total of 66 instances of each function being invoked.

Getting back to the original post, in the case of the recursive function that increments the value for each iteration, the max value could be passed via a parameter instead of using a global. If the max value parameter is passed via the stack for each iteration, it would increase the overhead. If the max value parameter is simply kept in the same register for all instances of the function, then there would be no significant overhead (for register based parameters (up to 2 in 32 bit mode, up to 4 in 64 bit mode) with Microsoft 32 bit compiler, use fastcall (/Gr) option, for Microsoft 64 bit compiler, fastcall is the default).

 

[MisterX]

Unless someone deleted a post, none of the posts in this thread include an example of summation via a for loop. The for loop in my post was used to invoke the recursive summation routines 11 times, to run the summation for 0->0 to 0->10 cases.

Sorry, that wasn't clear to me (each time you call one of the functions, it requires i+1 recursive steps, and since your were summing these number of steps for n from 0 - > 10, getting lu and ld is similar to solving the OP's problem).

Please initialize variables before using them in C or C++.

 

[rcgldr]

Please initialize variables before using them in C or C++.

I missed that when modifying Xtami's code to show the number of instances were the same for both functions. Normally I declare those type of variables as static which initializes them to zero. I updated my previous post to properly initialize them.

 

[chiro]

In class, we're learning about recursive functions. One example given was figuring out 1 + 2 + 3+ 4 + 5 + 6 + 7 + 8 + 9 + 10. My professor stated to address this, we start with 10 in the function and decrement for the next recursive call, so 10 + f(9). He said going the other way would be considered more work, 1 + f(2), and a recursive function should do the least amount of work possible. I don't get why this is considered more work. It would be the same number of steps either way. What's the benefit of counting down instead of up in terms of the workload? Thanks.

Hey Jimmyk and welcome to the forums.

For this example, it should not matter: there will be the same number of evaluations no matter how you evaluate it. It might have been more intuitive to go left to right, because it seems natural to do since we do that all the time (mathematical formulas, writing words, and so on).

The comment about doing the minimal amount of computations is probably the most important. In this specific example, there is a one or two line calculation that will figure out the answer [(n+1)n/2 I think it is], so in this particular case you don't need recursion. But many things out there require it, since many problems don't simplify like your example, and recursion provides a really powerful tool.

With regards to doing recursion problems in the future, it can be handy to think of your data in terms of some kind of "chain". Each recursion step divides up the chain, and how you divide up the chain can help you set up your function parameters. It is a personal style comment, but if you end up using common templates like these with all your recursive functions, it will help you understand problems with code that you wrote literally months ago or even last year.

Good luck in your learning.

 

[rcgldr]

My professor stated to address this, we start with 10 in the function and decrement for the next recursive call, so 10 + f(9). He said going the other way would be considered more work, 1 + f(2) ... What's the benefit of counting down instead of up in terms of the workload?

My guess is that the professor was considering "semi" generic functions where the upper value is an input while the lower value is fixed (zero in this case). The decrement version only needs one parameter, while the increment version needs two:

int rsumdec(int i){
    if(i>0)return i+rsumdec(i-1);
    return i;} 

// versus

int rsuminc(int i, int n){
    if(i<n)return i+rsuminc(i+1, n);
    return i;}

However if the compiled code for rsuminc() leaves n in a register as opposed to storing a copy of it on the stack for each instance of rsuminc(), then there's no additional overhead. If the summation is more generic where both the lower and upper input parameters are variable, then both functions would need two input paramters and it wouldn't matter if you incremented or decremented, and rsumdec() would look like this:

int rsumdec(int i, int n){
    if(n>i)return n+rsumdec(i, n-1);
    return n;}