4 replies to this topic

[psycho]

Hi there,
I have to write a program using a recursive function to return the largest number within an array of bytes.
Here's what I have:

Const
dim = 5;

Type
tvVector = array[1..dim] of byte;

Procedure Asignacion(var vVector : tvVector);
var i : byte;
Begin
  For i := 1 to dim Do
    Begin
      writeln('Input a number for ',i,' :');
      readln(vVector[i]);
    End;
End;

Function Maximo(i : byte;var max : byte; var vVector : tvVector):byte;
Begin
  While(i <= dim) Do
    If vVector[i] > max then
      Begin
        max := vVector[i];
        Maximo := Maximo(i+1,max,vVector);
      End
    Else
      Maximo := Maximo(i+1,max,vVector);
Maximo := max;
End;

var
i,max,res : byte;
vVector : tvVector;
Begin
Asignacion(vVector);
i := 1;
max := 0;
res := Maximo(i,max,vVector);
writeln('The largest number is: ',res);
readln();
End.

The problem is that once the program calls upon the function, it will get into an infinite loop.
Any suggestions?
Thanks in advance!

[chili5]

I don't know much of anything about Pascal but I can help with the general logic.

The function prototype should accept the index of the array, the current max value and the vector.

The exit strategy for the recursion should be if we have scanned through the entire vector.

Then if v[i] is greater than max, update max and call the function again. Otherwise go to the next element.

From looking at your function it looks like it should almost work.L From what I can see is you are doing a loop (while i <= dim) but in that loop i is nefver increasing which explains the infinite loop.

Try eliminating that loop. Then adding the exit strategy should make your function work.

Function Maximo(i : byte;var max : byte; var vVector : tvVector):byte;
Begin 
    If i >= dim Then
        End 

    If vVector[i] > max then
      Begin
        max := vVector[i];
        Maximo := Maximo(i+1,max,vVector);
      End
    Else
      Maximo := Maximo(i+1,max,vVector);
Maximo := max;
End;

Something like that. My function in Java looks like this:

static int max(int i, int max, Vector<Integer> v) {
        if(i >= v.size()) return max;

        if(v.get(i)>max) {
            max = v.get(i);
        }
        return max(i+1,max,v);
    }

Can't help with the Pascal but that is the idea that you want. Just lose the loop and your code is almost right. :) Hope that helps.

[psycho]

Great!!
Thanks for the info, I got it working now.
I just had to change the while for an if.

[chili5]

You're welcome. :)

[LuthfiHakim]

Hello,

I'd like to mention a couple of things.

• In your case, the use of recursive is not justifiable. So unless it was a study related assignment, you'd better use simple iteration (while.. do or for.. loop).
  
• Utilization of limit checker routines (such as Low() and High()) is preferable for then you'd be independent on declaring constants. In your case, please change
  

  if i >= dim then

  into
  

  if i > High(vVector) then 

  as you can see, by using High(), your code now is easier to refactor. Because now you don't have to care whether the passed array is really in "1..dim" range or not, for now it works with any size of array.
  
  So your recursive function could be refactored into:
  

  function Maximo(const AIndex: byte; const AMax: Byte; const AVector : tvVector): Byte;
  
  begin
  
    if AIndex > High(AVector) then
  
      Result := AMax
  
    else
  
      Result := Maximo(AIndex+1, Max(AMax, AVector[AIndex]), AVector);
  
  end;

  
  Note that I am using Max() routine from Math unit. So you need to add Math to your uses list.
  
  And the call to that function can be simplified, from:
  

  res := Maximo(i,max,vVector);

  into
  

  res := Maximo(Low(vVector), 0, vVector);

Last notes regarding recursive,

• While you can, avoid it. It's actually expensive way to do iteration. Remember that each call (and return) involves overheads (at least some stack operations).
  
• The first thing to do when you decide to do something recursively is to CAREFULLY define the exit condition. Otherwise it will enter infinite loop or hitting stack overflow or insufficient memory error