tail recursion

[transplantedNYr]

I have to take the following code and make it tail recursive.

I am not looking for the answer, but how to find the answer. How to work through this to understand what I need to do. Our hint is that we can change the parmeters of the function, like changing the number/type of the functions arguments.

// this program returns the maximum value in an array
int max(int numbers[ ], int size) {
if (size == 1)
return *numbers;
int first = *numbers;
int rec_max = max(numbers+1, size-1);
if (first > rec_max) return first;
return rec_max;
}

[dmanw100]

If you change the numbers[] array so the first element stored is the length of the array, then you can eliminate the second variable and simply keep passing the array to the function.

[transplantedNYr]

The variable 'size' is the length of the array.

Do you mean...?

numbers[0] = Size

not sure I follow...

[transplantedNYr]

I think I got something.

int max(int numbers[ ]) {
numbers[0] = size;
if (numbers == size)
{return *numbers;}
return max(numbers+1);
}

or would the terminating variable be if (*numbers=size) {...} else max(numbers+1)

I do not think this is right, but it is me trying to think this out.

[transplantedNYr]

So I do not think I can take size out of the function as the function needs to know when to stop. I can not arbitrarily change the size of the array, it should be pass when function is called.

So my thought is that I should compare numbers with numbers plus one.

int max(int numbers[ ], int size, int first) {
if (size == 1)
return *numbers;
int first = *numbers;
if (first > numbers+1)
return first;
return max(numbers+1, size-1, first+1);}

I get a I am comparing a int to a pointer so it is not working, but I think this is basically what i want to do.

Basically I need an extra variable to declare in the function to compare first which equals *numbers

[shrughes]

dmanw100's answer is completely wrong and nonsensical.

When transforming something to tail-recursive form, it helps to ask, "What information do I need so that no work needs to be done after this function call returns?" That is, "What information makes it possible for this function to return with the final answer?" This question is relevant, because when you write a function in tail-recursive form, every recursive call you make will return the final answer.

When walking through an array, for your problem, you only need to know: the address of the first element of the array, the number of elements remaining in the array, and the maximum element seen so far. These pieces of information should be the parameters to your function.

[transplantedNYr]

Shrughes, Thanks, I thought that was some bogus advise...

Here is my thought...

int max(int numbers[ ], int first, int size) {
if (size == 1)
return *numbers;
first = numbers[0];
next = numbers[1];
if (first > next) return first;
return max(first+1,next+1,size-1;)

Would this work. I can not test it while at work...

[stilllearning]

Are your numbers sorted in the descending order ? Because otherwise when you do if (first > next) return first; it will always return the larger of the two numbers : test case 2, 1, 3, 4, 5, will return 2 as max.

Also look at this max(first+1,next+1,size-1); the first argument to your max function is the numbers array, and you are trying to pass the integer first + 1 ? If first < next then you can skip first, but do you want to skip next also ?

You need to understand the primary logic of how to make this work ..
Hint : Compare the first and the last number in the array

[transplantedNYr]

First let me thank you for your help... in helping me understand this better...

no I do not believe we know if the numbers are sort in any order.

You are correct with pointing out my flaw of if first > next.

My thought behind "max(first+1,next+1,size-1); " was to compare first compare first and next for each recursive call.

Now that you point this out I notice this is incorrect in the logic.

If I was to compare numbers[first] to numbers[last] wouldnt I have the same problem if
if the first number was 2 and the last number was 1 or 0?

Here is where my thought is now...

int max(int numbers[ ], int size, int prev) {
if (size == 1)
return *numbers;
int first = *numbers; //or numbers[0];
prev = numbers;
return max(numbers+1, prev-1, size-1);

I know when i figure this out i will see how easy it was. 'doh!

[stilllearning]

Lets try some pseudocode here. Your terminating condition should be size == 0, because the array elements go from 0 to size - 1;

max (arrayNumbers, arraySize){
  if (arraySize == 0)
    return arrayNumbers[arraySize];
 else
    if (ArrayNumbers[0] > ArrayNumbers[size])
    // exclude the last element 
    max(arrayNumbers, arraySize - 1);
    else
    // exclude the first element 
    max(arrayNumbers + 1, arraySize - 1);
  done;
}

[transplantedNYr]

Like I said, 'doh!

Thanks for your help.