Thread: Add elements through array recursively

Hello all, I am having tremendous problems writing this program. I know that I should be able to write this proram in 15 lines (maybe even less) but I am having trouble finding the correct method to write it. I've been trying to write it for a few days now and am frustrated because I know that it is a simple mistake that I am making.
I am trying to write a program that sums the elements of an array.
It's supposed to take 3 arguments that I believe I entered correctly
m: start position of array (1<=m<=10
n:end position of array (1<=n<=10 and m<=n)
int_array[]:integer array

Basically I am trying to get the program to add the elements (m through n) using recursion.
Another part of this is that I have to use the pointer but I'll figure that one out later

Just please let me know if I am way off because I havent had too many problems with C++ up until now. Should I start from scratch?? Is my sum function all wrong??

In advance, Thank you for any help you can provide

Code:

#include <iostream.h>

int sum(int); // function prototype

int main()
{
	int int_array[10]={1,2,3,4,5,6,7,8,9,10};
  int m,n;
	
	cout << "Please enter the starting position: ";
   cin >> m;
	cout<< "Please enter the end position:  ";
	cin>>n;
return 0;

 // end main


}

int sum ()

{  
   if ( 1 <= m<=10 && 1<=n<10 && m<=n)  
      return int_array[m]+int_array[n];

  

   // recursive step
   else             
      return 1;

} // end function

Personally, I'd use a loop to do this rather than a recursive function, but you can probably use recursion if you wish.

In general, recusive functions need to have a starting and ending state and something to do in between. One of the steps in between is to call the function again using a new value generated within the called function.

I would validate m and n outside of sum(). I would pass sum() the values of m and n and the array itself. Inside sum() I would have a variable called temp. If m == n I would return the value of array[m]. Otherwise I would assign temp the sum of the value of array[m] and the return value of sum() called using the next value of m, which I would generate by the post increment operator. In this way the sum would be calculated backwards, starting with the value of array[n] and adding the value of array[n -1] with each unwinding of the recursive calls.

Code:

int sum(int, int, int*);

int main()
{
//declare int_array and obtain and verify m and n
//then
int answer = sum(m, n, int_array);
//do something with answer
}

int sum(int m, int n, int * int_array)
{
   int temp = 0;
   if(m == n)  
      return int_array[m];
   else
      temp = int_array[m++] + sum(m, n, int_array);
      return temp;
}

If m were 0 and n were 2 with int_array as in your post, then there will be three calls to sum(). at the third call to sum() m will equal n, so the value of int_array[2] will be returned to the second call to sum() and added to int_array[1] making temp = 2 + 3; then temp will be returned to the first call of sum() making temp = 1 + 5. Then temp will be returned to main() where it will be assigned to answer.

Thank you very much "elad". Thanks to your notes, I was able to see where I went wrong and rewrite the code so that it would fit the program I was trying to write. I am still missing a line or two but am definitely on the right track now.

Thanks

Originally posted by elad

Code:

int sum(int m, int n, int * int_array)
{
   int temp = 0;
   if(m == n)  
      return int_array[m];
   else
      temp = int_array[m++] + sum(m, n, int_array);
      return temp;
}

We can simplify this by removing temp:

Code:

int sum(int m, int n, int * int_array)
{
   if(m == n)  
      return int_array[m];
   else
      return int_array[m++] + sum(m, n, int_array);
}

Also possible, though less readable, is:

Code:

int sum(int m, int n, int * int_array)
{
   return m==n?int_array[m]:int_array[m++] + sum(m,n,int_array);
}

You are missing a sequence point.

int temp = int_array[m++];
return temp + sum(m,n,int_array);

Though the whole thing reeks of homework.

return m==n?int_array[m]:sum(m,(n+m)/2,int_array) + sum((n+m)/2+1,n,int_array);