Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Return largest integer in an array using recursive function

array recursive

  • Please log in to reply
4 replies to this topic

#1 psycho

psycho

    CC Newcomer

  • Just Joined
  • PipPip
  • 11 posts

Posted 21 July 2010 - 06:44 PM

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!
  • 0

#2 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 30 July 2010 - 04:34 PM

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.
  • 0

#3 psycho

psycho

    CC Newcomer

  • Just Joined
  • PipPip
  • 11 posts

Posted 01 August 2010 - 03:45 PM

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

#4 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 01 August 2010 - 04:40 PM

You're welcome. :)
  • 0

#5 Luthfi

Luthfi

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1320 posts
  • Programming Language:PHP, Delphi/Object Pascal, Pascal, Transact-SQL
  • Learning:C, Java, PHP

Posted 30 October 2010 - 12:36 AM

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

  • 0





Also tagged with one or more of these keywords: array, recursive

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download