recursion

hello,
I'm new here and I have a little problem:
I need to write a code for a PURE recursive function.
I have an array of integers and it's size and the function that's I need to write needs to find the longest sub-sequance of inceasing items and return it's length.
It should be written in one function only (I can add as much parameters to the function as I need) and there is a rule of no loops at all!
I wrote 2 versions for the function but both of them crash at some cases.
Can someone please help me?
thanks,
s.

Post your code

It would be easier for someone to help if you post your 2 versions up on the board here. Read this about posting code.

Quote:

---

Originally Posted by rabers

hello,
I'm new here and I have a little problem:
I need to write a code for a PURE recursive function.
I have an array of integers and it's size and the function that's I need to write needs to find the longest sub-sequance of inceasing items and return it's length.
It should be written in one function only (I can add as much parameters to the function as I need) and there is a rule of no loops at all!
I wrote 2 versions for the function but both of them crash at some cases.
Can someone please help me?
thanks,
s.

---

I looked in my crystal ball and see that your first function has an error in line 9 and the second function the same error in the line 13.

Will it help you?

Code:

---

int max_set(int arr[],int size,int startInd,int index,int temp,int max)
{
        if (size>1){
                if(startInd>=0){
                        if(arr[startInd]>=arr[index])
                                return max_set(arr,size,index,index-1,temp+1,max);
                        else
                                return max_set(arr,size,startInd,index-1,temp,max);
                }
                else{
                        if(temp>=max)
                                return max_set(arr,size-1,size-2,size-3,0,temp);
                        else
                                return max_set(arr,size-1,size-2,size-3,0,max);
                }
        }
        return max;
}

---

this code starts from the end of the array and crashs at cases like:
1 2 3 0 10 12 9
because when it reachs to "0" it dosen't skip it but count it and dosen't continue cause its the smallest item at the series.

Code:

---

int max_set(int arr[],int size,int start,int startPos,int startInd,int index,int temp,int max)
{
        if(start<size){
                if(index<=size-1){
                        if(arr[startInd]<=arr[index]){
                                if(arr[startInd]<=arr[index+1])
                                {       
                                        if(arr[index]<=arr[index+1])
                                                return max_set(arr,size,start,startPos,index,index+1,temp+1,max);
                                        else
                                                return max_set(arr,size,start,startPos,index+1,index+2,temp+1,max);
                                }else
                                        return max_set(arr,size,start,startPos,index,index+1,temp+1,max);
                        }else
                                return max_set(arr,size,start,startPos,startInd,index+1,temp,max);
                }else
                {
                        if(startPos<=size-1){
                                if(temp>=max)
                                        return max_set(arr,size,start,startPos+2,startPos+1,startPos+2,1,temp);
                                else
                                        return max_set(arr,size,start,startPos+2,startPos+1,startPos+2,1,max);
                        }else
                        {
                                if(temp>=max)
                                        return max_set(arr,size-1,start+1,start+2,start+1,start+2,1,temp);
                                else
                                        return max_set(arr,size-1,start+1,start+2,start+1,start+2,1,max);
                        }
                }
        }else
                return max;
}

---

this code starts from the beginning of the array and crashes at cases like:
1 21 3 33 6 53 9 18
because it doesn't skip items like 21 and 33 that even they are greater then 1 choosing them isn't good cause i need to skip 'em and count 1 - 3 - 6 - 9 - 18
i tried to change my code and use some indicator for the last Position (used in this function and I'm not sure I need that) so if the series isn't long enough I'll skip and item and search again but i don't know how much indicators I'll need.
how can I deal with problem?

in the first function you never check that your index is >= 0 when accessing arr[index]

add some trace at the beginning of the function like

Code:

---

printf("Enter the max_set(arr=%p,size=%d,startInd=%d,index=%d,temp=%d,max=%d)\n",
(void*)arr,size,startInd,index,temp,max);

---

and see at what value you get the crash and why you get them

What vart says about using a printf to trace the calls is very important. Here's another tip: rather than doing this

Code:

---

if(start<size){
    [your entire function here]
}else
        return max;

---

Why not write:

Code:

---

if (start>=size) return max;

---

The execution is identical but the second version will save you a nest which makes the code more manageable.


ps. what you've got thus far is way too crazy. I just wrote this function in less than ten lines. Here's the prototype and the call:

Code:

---

int setlength (int *ray, int len, int index, int count, int high);

int main() {
        int ray[]={0,4,12,2,3,4,5,7,9,10,14};
        printf("answer=%d\n",setlength(ray,11,0,1,1));       
        return 0;
}

---

Output: answer=4
The function always returns high. count keeps track of the current number of numbers in a series. No loops, all recursion.

Quote:

---

Originally Posted by vart

in the first function you never check that your index is >= 0 when accessing arr[index]

add some trace at the beginning of the function like

Code:

---

printf("Enter the max_set(arr=%p,size=%d,startInd=%d,index=%d,temp=%d,max=%d)\n",
(void*)arr,size,startInd,index,temp,max);

---

and see at what value you get the crash and why you get them

---

yes, but i know why it crash but i don't know how fix it.
it goes from the last item to the begining and add to the counter when ever the previous item is smaller but if the item is very small but the other item before it are smaller it does'nt count 'em.
at: 1 2 3 0 10 12 9 it goes from 9 and count 2 (9 and 0) and then from 12 to 10 and 0 instead of skiping 0 and count 12 - 10 - 3 - 2 - 1
how do I fix that?
or- maybe someone has a different way?
thanx

Quote:

---

Originally Posted by MK27

What vart says about using a printf to trace the calls is very important. Here's another tip: rather than doing this

Code:

---

if(start<size){
    [your entire function here]
}else
        return max;

---

Why not write:

Code:

---

if (start>=size) return max;

---

The execution is identical but the second version will save you a nest which makes the code more manageable.


ps. what you've got thus far is way too crazy. I just wrote this function in less than ten lines. Here's the prototype and the call:

Code:

---

int setlength (int *ray, int len, int index, int count, int high);

int main() {
        int ray[]={0,4,12,2,3,4,5,7,9,10,14};
        printf("answer=%d\n",setlength(ray,11,0,1,1));       
        return 0;
}

---

Output: answer=4
The function always returns high. count keeps track of the current number of numbers in a series. No loops, all recursion.

---

the answer is wrong
what about the subsequance: 0-2-3-4-5-7-9-10-14 which is 9 items long instead of 4

Quote:

---

Originally Posted by rabers

the answer is wrong
what about the subsequance: 0-2-3-4-5-7-9-10-14 which is 9 items long instead of 4

---

Following this logic it would actually be 10, because you left out 12. I was assuming "longest subsequence" meant 2-3-4-5, the same way you would say that "this and that" contains the substring "and" or "hat" but not "sat" or "tin".

I guess I misunderstood what you were asking for -- but are you sure you are correct about what you are asking for? This is a very strange way to ask for what amounts to the number of unrepeated numbers (the only number that repeats above is 4, so of course you can form a sequence with the remaining numbers). Why would someone ask for something like the "length of the longest subsequence" when what you mean is the number of unique numbers? Either chasing a "sequence" here is irrelevant to the task or you have misunderstood your assignment.

Quote:

---

I have an array of integers and it's size and the function that's I need to write needs to find the longest sub-sequance of inceasing items and return it's length.
It should be written in one function only (I can add as much parameters to the function as I need) and there is a rule of no loops at all!

---

How about you solve it using iteration first and then convert the answer to a recursive-only solution later, before you hand it in?

this problem has already been discussed, search the board if you're looking for hints and tests.

Quote:

---

Originally Posted by MK27

Following this logic it would actually be 10, because you left out 12. I was assuming "longest subsequence" meant 2-3-4-5, the same way you would say that "this and that" contains the substring "and" or "hat" but not "sat" or "tin".

I guess I misunderstood what you were asking for -- but are you sure you are correct about what you are asking for? This is a very strange way to ask for what amounts to the number of unrepeated numbers (the only number that repeats above is 4, so of course you can form a sequence with the remaining numbers). Why would someone ask for something like the "length of the longest subsequence" when what you mean is the number of unique numbers? Either chasing a "sequence" here is irrelevant to the task or you have misunderstood your assignment.

---

I didn't misunderstand the task. that's what I was asked for to do.
12 isn't relevant here cause i need to find a sequance of integers that's are increasing. when the order of the item at the array matters. i cant count an item that's smaller then a previous item i counted.
thnx anyway

Quote:

---

Originally Posted by rabers

I didn't misunderstand the task. that's what I was asked for to do.
12 isn't relevant here cause i need to find a sequance of integers that's are increasing. when the order of the item at the array matters. i cant count an item that's smaller then a previous item i counted.
thnx anyway

---

Sorry for wasting your time;) I don't do math, so I guess I just guessed what "the longest sub-sequance of inceasing items" might mean. With no loops! But that is tough and I gave up after staring at a sequence for about half an hour. Would love to see the solution...