Conflict in returning a value through a recursive function

Hello,
I need to write a recursive function, which gets as an input the
address of an array of numbers and it's size, and returns the size of
the longest continuous increasing sub-sequence in it.

There's also a limitation, that I can't use loops or other functions.
I also can't use pointers to outer variables, because I'm not supposed
to change the main function.

So far I've managed to make this work only for the case in which
two sub-sequences are separated by only 1 number which breaks the sequence, and of course the easy case in which all of the array is an increasing sequence or it's starting to increase from a certain point and then stops.

The more complicated case, is when I've got for example this array:

Code:

---

{1, 2, 3, 0, 0, 4, 5, 6}

---

Here the output should be 4

Code:

---

({0,4,5,6})

---

,
but no matter from which direction the recursive function goes, left to right

Code:

---

(function(address+1, size-1))

---

or right to left

Code:

---

(function(address, size-1))

---

, I don't know how can I both return the size of the largest previous sub-sequence found, and also start counting the next possible sub-sequence and comparing them, without increasing the largest size already found.

So what I'm actually asking for is help with the algorithm that can solve the more complex case. I would like to figure out the code myself, but I'm having trouble thinking of a successful recursive algorithm.

You can use a helper function to set up the recursive function. I was able to solve it with this structure:

Code:

---

#include <stdio.h>
 
int func_rec(const int *a, int size, int cnt, int longest) {
    // ...
}
 
int func(const int *a, int size) {
    return size <= 0 ? 0 : func_rec(a + 1, size - 1, 1, 1);
}
 
int main() {
    int a[] = {1, 2, 3, 0, 0, 4, 5, 6};
    int size = sizeof a / sizeof a[0];
    printf("%d\n", func(a, size));
}

---

Thanks,
but I'm not allowed to use helper functions.
Also, I'm given the function's signature in advance and I'm not allowed to change it.
It looks like this:

Code:

---

int function(int a[], int size);

---

The only thing I know for sure is the array's max size possible, which is defined by #define.
Thought about using it (or anything else) somehow to find the address of the first element in the array
even If I'm deep inside the recursive function, but without success so far.

It's extremely common to use a helper function with recursion. Are you sure you aren't allowed? I don't see how you can do it without a helper function unless you use global variables, which would be idiotic.

And the signature I used is essentially the same as the one you show. Just change it.

@ido.r

I was about to post your recent point, that you can't use functions or loops, to @john.c.

I'm a strong advocate of an interface function for recursion, but alas that is out here.

Let me walk through an idea as it evolved while I was out doing stuff, which first explores ways to at least find the answer, then fold that into a compliant solution that seems to fit the requirements.

First, if we could use loops, this gets the answer as best I can test in short time:

Code:

---

int lenseries1( const int *a, int size )
{
 if ( size < 1 ) return 0;

 int len = lenseries1( a + 1, size - 1 );

 int val = a[ 0 ];
 int seqcount{ 1 };


 for( int pos = 1 ; pos < size; ++pos )
    {
    if ( val >= a[ pos ] ) break;

    val = a[ pos ];
    ++seqcount;         
    }

 if ( seqcount > len ) return seqcount;
 return len;

}

---

With a loop being a disqualifier, I decided to try an experimental version that violates the rules to prove a hunch:

Code:

---

int lenseries4( const int *a, int sz, int curcount, int maxcount )
{
 if ( sz < 2 ) return maxcount;

 bool is_series = a[ 0 ] < a[ 1 ];

 if ( is_series ) curcount++;

 if ( curcount > maxcount ) maxcount = curcount;

 if ( !is_series ) curcount = 1;

 maxcount = lenseries4( a+1, sz-1, curcount, maxcount );

 return maxcount;

}

int lenseries( const int *a, int sz )
{
 int maxcount{0};

 return lenseries4( a, sz, 1, maxcount );
}

---

This shows a need to preserve "maxcount" ongoing, but we don't have quite enough parameters.

So, unless this is considered "cheating", I wrapped the values into the size parameter using some simple "bit fiddling", which assumes the max size will be < 255 (but variations are certainly possible to expand that limit)

Code:

---

const int mask_h{ 0x00ff0000 };
const int mask_l{ 0x0000ff00 };
const int mask_s{ 0x000000ff };

int lenseries5( const int *a, int sz )
{
 int size = sz & mask_s;
 int curcount = (sz & mask_l) >> 8;
 int maxcount = (sz & mask_h) >> 16;

 if ( curcount == 0 ) curcount = 1;

 if ( size < 2 ) return maxcount;

 bool is_series = a[ 0 ] < a[ 1 ];

 if ( is_series ) curcount++;

 if ( curcount > maxcount ) maxcount = curcount;

 if ( !is_series ) curcount = 1;

 sz = ( size - 1 ) | ( curcount << 8 ) | ( maxcount << 16 );

 return lenseries5( a+1, sz );
}

---

So here is the same plan as the previous (lenseries4 and interface function), but this uses the size integer to pack in size, curcount and maxsize, using the return to preserve maxsize as found going in.

I've written this in over-simplified style for illustration.

See if it violates any rules or the spirit of the restrictions.

@Niccolo
Thank you very much for your detailed and clear response.
Your last code seems very close to the general structure in which my answer should be written,
but unfortunately for me, there are few syntaxes there that I haven't learned in my course and don't know them,
such as "mask" and "& mask", seperating with one "|".

I believe that the solution should be somehow simpler, using the basic tools I've been given in my course.

I thought that what would help me the most will be if there's a way to find the address of the first element in the array,
even from inside a few entrances to the recursive function while increasing the address input.
Couldn't find such a way when I tried, and if there isn't one than perhaps it's not the solution.

If you have any simpler idea I would love to see it, and meanwhile I guess I should review
my course material thoroughly before trying again.

Mask is part of a variable name I made up. Mask_s, for example, is 0x0ff, or 255 decimal. All three "masks" are just integers.

The & and | characters are operators in the same level as + and -, except they work on bits as booleans rather than addition or subtraction.

Are you sure you haven't covered the logical operators like and/or/xor/not?

It's the >> and << that may be less familiar - shifting, which are multiplications in powers of 2.

I'll contemplate on the points about limitation upon what's taught in class, but since I'm not in class I'll have to guess a little.

Frankly, I just woke up, and I'm on my first cup of coffee - those who know me would warn I'm not actually conscious. However, the one other idea in my mind, which is only the bare opening of one, a ghostly hint at the moment and might actually be a dream....

...since the size parameter is an integer, you can encode ONE piece of information rather simply. It can be negative to signal a condition or state of the algorithm, while it's absolute value still functions as "the size".

I'm not even aware why I want to such a feature, so maybe the third coffee wakes me up enough to remember, but I'm thinking of a second recursive call working in a different direction.

In other words, if size is < 0, recursion is working in one way (and abs(size) still measures), but if size > 0 recursion is working another way - I'm just not awake enough to remember why I thought that was useful.

...and abs(size) is simple to implement in code, so you don't have to call abs

Ok, 3rd cup's a charm.

The "negative size" pattern is perhaps a minor player here.

An obvious option is this:

Code:

---

int lenseries6( const int *a, int size )
{
 static int curcount = 1;
 static int maxcount = 0;

 if ( size < 2 ) return maxcount;

 bool is_series = a[ 0 ] < a[ 1 ];

 if ( is_series ) curcount++;

 if ( curcount > maxcount ) maxcount = curcount;

 if ( !is_series ) curcount = 1;

 return lenseries6( a+1, size - 1 );
}

---

The point here is that there will be no means of determining a max count without some storage. I don't see how you can implement a routine which catches all cases without it. For example, in a larger series where there could be several groups of 2 or 3 sequences, but a length 4 in the center is the worst case to study.

So, static declarations take that position without bit fiddling.

However, there's a problem. They only initialize once, so the function could only be called once. So....

Code:

---

int lenseries7( const int *a, int sz )
{
 static int curcount = 1;
 static int maxcount = 0;
 int size = sz;

 if ( sz < 0 )
 {
  size = -sz;
 }
 else
 {
  maxcount = 0;
  curcount = 1;
 }

 if ( size < 2 ) return maxcount;

 bool is_series = a[ 0 ] < a[ 1 ];

 if ( is_series ) curcount++;

 if ( curcount > maxcount ) maxcount = curcount;

 if ( !is_series ) curcount = 1;

 return lenseries7( a+1, -(size - 1) );
}

---

In this version the size is "transmitted" through the recursive calls as a negative value, to indicate it is not the FIRST call of the function. This triggers re-initialization of the static values.

It does mean this can't be threaded.

@Niccolo
Looks good! but still we haven't learned static variables and not supposed to use them :p
But, the good news is that today in class they gave us a big hint and I managed to make this work with a very simple algorithm
that doesn't require anything sophisticated regarding to the syntax.

The recursive algorithm is:
1. The recursive data - Given the size of the longest sequence in the array without the first element, and given the size
of the longest sequence in the array without the last element, return the maximum between them.
2. If the whole current array is one increasing series, it means that both longest sequences that returned are the same,
and also that they both lack one number, so return the maximum and add 1.
3. Stopping conditions:
a. If the size is 0 return 0;
b. If the size is 1 return 1;
c. If the size is 2 return 2 if a[0] < a[1], else return 1.

So after checking a few examples and drawing the call stack diagram for a small example I found out that this will always work.

I had thought of the idea of "packing" multiple values into the size parameter, but obviously that's totally ridiculous unless this is just supposed to be some kind of pointless puzzle! But maybe it is.

I had also thought of statics, but you can't reset them.

Globals are the only "answer" to this basically stupid question.

An "interface function" (good name) is the real answer.