Longest Index - Recursion

Question

Hello, I need to write a code for this assignment, subject of study is recursive methods:

Example: Consider arr={0,5,1,1,2}. Indices 0,2 and 3 are well-placed:

• Index 0 is well-placed since P0=0.
• Index 1 is not well-placed, since P1=5>1. Since all elements are positive, it’s impossible to find a sequence starting at index 1 that can be summed to 1.
• Index 2 is well-placed since P2+P3= 2.
• Index 3 is well-placed, since P3 + P4 = 3.
• Index 4 is not well-placed: We can’t find a sequence starting at index that can be summed to 4 – that’s because P4 is the last element in the array, and it’s only 2.

We define ‘well-placed length’ of a well-placed index to be j-i+1 – The length of the sequence that when summed shows that the index is well placed. It is possible an index is well-placed with more than a single sequence of elements. The ‘well-placed length’ in that case is the maximal length of the various sequences defining the index as ‘well-placed’.

Example: Looking at previous example:

• Index 0 well-placed length is 1 (i=0, j=0, j-i+1 = 1).
• Index 2 well-placed length is 2 (i=2, j=3, j-i+1 = 2).
• Index 3 well-placed length is 2 (i=3, j=4, j-i+1 = 2).
• For indices 1 and 4, well-placed length is not defined, since the indices are not well-placed.
• Consider arr= {0,5,1,1,2,0} – index 3 well-placed length is now 3 (i=3, j=5, j-i+1=3). Another sequence that defines index 3 as well-placed is (i=3, j=4, j-i+1=2) as before, but we’ve defined well-placed length to be the maximal value for the index.

The ‘maximal well-placed length’ is the maximum between the well-placement length of all well-placed indices in arr. If no index in the array is well-placed, the maximal well-placed length is considered to be zero.

The function should return the maximal well-placed length.

Example: For previous examples, the return value of longestIndex should be 2, since that is the maximal well-placed length of any well-placed index in the array.

Restrictions: you are not allowed to change array; you are not allowed to use more than 1 additional (helper) function that can be reached from longestIndex. No iteration allowed.

This is the code i wrote:

int longestIndexHelper(int arr[], int length, int old)
{
    if(length==0)
    return 0;
    if((arr[length]+arr[length-1]==length-1)||
       (arr[0]==0)&&(old!=0)&&(old-length==1))
      return (longestIndexHelper(arr, --length, length)+1);
}

int longestIndex(int arr[], int length)
{
    return longestIndexHelper(arr, length, length);
}

Obviously, it does not work :) Could someone please try to help?

Answer 1

No iteration allowed.

This is an entirely artificial restriction that pushes us into recursion when it's clearly an inferior solution in this case. When will college professors start to go for something that actually wants a recursive solution (say, tree walking) for these assignments?

I'd personally do this by writing the iterative version and transforming it into a tail-call recursive one. just to satisfy this arbitrary requirement. And leave the iterative version in there commented-out just because.

Anyway, the reason yours doesn't work is that it only ever checks for well-placed matches of length 2.

EDIT: Here's a quick outline of my recursive solution:

int longestIndex(int arr[], int length) {
    if(length == 0) return 0;
    int thisLongestIndex = longestIndexHelper(
        /*whatever parameters you need in order to call it on the first element
                  in the array*/
        );
    return max(thisLongestIndex, longestIndex(arr+1,length-1));
}

Where longestIndexHelper will work out the longest match for the first element in the array.

Answer 2

I'm not going to debug your whole function, but an obvious potential flaw is that in some cases your helper function doesn't return any value.

You need to consider how the recursion will continue when the if () test fails.