solving problems recursively in C

Question

Our professor gave us the following assignment:

A "correct" series is one inwhich the sum of its members equals to the index of its first member.
The program is supposed to find the length of the LONGEST "correct" series within a series of n numbers.

for example: if the input series would be arr[4]={1, 1, 0, 0} the output (longest "correct" series) would be 3.
arr[0]=1. 0!=1 therefore the longest series here is 0.
arr[1]=1,and 1=1. but the follwing members also sum up to 1 as shown below:
1=arr[1]+arr[2]+arr[3] = 1+ 0 + 0, therefore the longest series here is 3.

the output in this example is 3.

That's what I got so far:

int solve(int arr[], int index, int length,int sum_so_far)
{
     int maxwith,maxwithout;

     if(index==length)
         return 0;

     maxwith = 1+ solve(arr,index+1,length,sum_so_far+arr[index]);
     maxwithout = solve(arr,index+1,length,arr[index+1]);

     if(sum_so_far+arr[index]==index)
         if(maxwith>maxwithout) 
            return maxwith;

     return maxwithout;

     return 0;
}



int longestIndex(int arr[], int index,int length)
{
     return solve(arr,0,length,0);
}

What am I doing wrong here? Thanks a lot for your time...

Harry

oh yeah, we aren't supposed to us eloops on this one. should have mentioned that earlier i guess...

Answer 1

It seems to me that the problem lies here:

if(sum_so_far+arr[index]==index)

You're comparing the sum so far with the current index, but you should be comparing it with the first index in the series. It seems to me that it would be better if you started with the last element of arr towards the first, instead of going in the natural order. That way you start summing elements up until the sum equals the current index.

Answer 2

First, write a function that tests a series of given starting index and given length for the "sum of its members" condition. Then, write a second function which looks for the longest series within your array where only the starting index is given (looping over the sub-series length in decreasing order should do it); this function can call the first one. At last, write a third function looping over all starting indexes, calling function number two.

Oh wait, there is no recursion needed any more, so a lot of brain-twisting is gone ... :-)

Answer 3

Hmm, there are several problems with this program.

Most obvious, "return maxwithout; return 0;" should give a compile error: There's no way to get to that last return statement.

Second, you're recursing in to solve on the "maxwith" path until you reach the end of the array. Then you're going to recurse into maxwithout, hitting it for the first time with index=4. I don't think this is going to work.

Frankly, I don't think this problem really calls for recursion. THe most natural solution would be a nested loop:

for (int start=0;start<length;++start)
{
  for (int end=start;end<length;++end)
  {
    // calculate the sum of arr[start]->arr[end] and compare to start
  }
}

Or something to that effect.

Did the problem call for solving it with recursion, or was that just your first idea at a good solution?

Edit

Okay, so you have to use recursion. I guess the point of the lesson is to learn to use recursion, not necessarily to solve the problem in the most natural or efficient way. (Personally, I think the teacher should have come up with a problem where recursion was a natural solution, but I guess we're not here to critique the teacher today.)

I don't want to do your homework for you, but I'll give you a hint. You can use recursion to simulate a loop by putting the break condition at the beginning of the function and putting the recursive call at the end of the function with a +1 parameter. That is, instead of writing

for (int x=0;x<10;++x) { ... whatever ...}

you can write

void forx(int x)
{
  if (x>=10)
    return;
  ... whatever ...
  forx(x+1);
}

So in this case I'd do something like:

void endloop(int start, int end)
{
  if (end>=arrayLength)
    return;
  ... work on running total ...
  endloop(start, end+1);
}

void startloop(int start)
{
  if (start>=arrayLength)
    return;
  endloop(start, start);
}
int main()
{
  ... setup ...
  startloop(0);
  ... output ...
}

Parameter lists are not necessarily complete. As I say, I don't want to do your homework for you, just give you a hint to get started.