4
\$\begingroup\$

Any tips on how to improve this simple recursion program?

#include <iostream>
#include <cstdlib>

using namespace std;

int findSum(int*, const int, int, int);

int main()
{
    int length = 5, sum = 0, n = 0;
    int list[length];


    for (n; n < length ; n++ )
    {
     list[n] = n + 1; //initializes array elements to 1,2,3,4,5
    }

    n = 0; 

    cout << findSum(list, length, n, sum) << endl;

    system("pause");
    return 0;
}

int findSum(int list[], const int length, int n, int sum)
{
    if (n == length) //if end of list has been reached, stop recursion
    {
        return sum;
    }
    else 
    {
        sum += list[n]; //adds list elements
        n++;            //increments list
        return findSum(list, length, n, sum);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Do you want to improve the recursion or do you want a better technique? \$\endgroup\$ – Martin York Oct 11 '11 at 23:04
  • \$\begingroup\$ Recursion must be used. \$\endgroup\$ – mwmnj Oct 12 '11 at 0:30
6
\$\begingroup\$

I think I'd prefer something like this:

int findsum(int const *list, int length) { 
    if (0 == length) 
       return 0;
    return list[0] + findsum(list+1, length-1);
}

This follows one of the typical recursive formulations -- basically a function that's almost like an inductive proof. Start by establishing a correct value for the simplest possible base case (or some obvious base case anyway), and then establish a pattern that's correct for some some sort of "Base+1" type of case.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.