# Board index » delphi » URGENT ** Problem with Iteration ** URGENT

## URGENT ** Problem with Iteration ** URGENT

Hi, I am a student with an assignment program I cannot get to work
properly. The assignment deals primarely with recursion, and that I
get to work.

The program is to make a list of numbers, write them to screen, ask
the user for a number and check the list if the number is there. The
checking should work both with recursion and iteration. The recursion
works every time, but the iteration routine rapports that the number
does not exist if it exists. This happens at more or less regular
intervals.

Control with indata is not an issue in htis exersice.

If you have a compier, pls try it out and give me som hint as to the
error.

The program is originally written in Norwegian, but I hope the
Try it out with different values for Max, just remember that it has to
be a multiple of 15!

With Max=30 the iteration makes an error on even places.
With Max=300 the mistakes comes more often.

Program Rekursjon;

Uses
crt;

Const
Max = 30;

Type
Table = Array [1..Max] of Integer;

Var
NumberList : Table;
L, R, x, RNumber, INumber : Integer;

{*********************************************}

Procedure WriteTable(Var NumberList:Table);

Var   i, k, l, value : Integer;

Begin
i := 1;
l := 1;
value := 1;

Writeln;
Write('  ');
For k := 1 to 15 do
Write(k:5);
Writeln;
Write('  ');
For k := 1 to 75 do
Write('-');
Writeln;

While i < Max do
Begin {while}
Write(l:2);
Write('|');
For k := 1 to 15 do
Begin {for}
value := value + (random(2) + 1);
NumberList[i] := value;
Write(NumberList[i]:5);
i := i + 1;
End;  {for}
Writeln;
l := l + 1;
End;  {while}
End;

{*********************************************}

Procedure FindNumberR(NumberList:Table;L, R, x:Integer; Var
RNumber:Integer);

Var
m : Integer;

Begin
If L = R then
Begin {if}
m := R;
If NumberList[m] = x then
Writeln('The number ', x, ' exists')
Else
Writeln('The number ', x, ' does not exist');
End   {if}
Else
Begin {else}
RNumber := RNumber + 1;
m := (L + R) div 2;
If NumberList[m] < x then
Begin
L := m + 1;
FindNumberR(NumberList, L, R, x, RNumber);
End
Else
Begin
R := m;
FindNumberR(NumberList, L, R, x, RNumber);
End;
End;  {else}
End;

{*********************************************}

Procedure FindNumberI(NumberList:Table;L, R, x:Integer; Var
INumber:Integer);

Var
m : Integer;

Begin
INumber := 0;
While (L < R) do
Begin {while}
INumber := INumber + 1;
m := (L + R) div 2;
If NumberList[m] < x then
L := m + 1
Else
R := m;
End;  {while}
If NumberList[m] = x then
Writeln('The number ', x, ' exists')
Else
Writeln('The number ', x, ' does not exist');
End;

{*********************************************}

Begin {Hovedalgoritme}
Randomize;
L := 0;
R := Max;
WriteTable(NumberList);
Writeln;
Write('Which Number do you want to find? ');
Writeln;
Writeln('Recursivt search:');
FinnNumberR(NumberList, L, R, x, RNumber);
Writeln('The recursion looped ', RNumber, ' times.');
Writeln;
Writeln('Iterativt search:');
FinnNumberI(NumberList, L, R, x, INumber);
Writeln('The iteration looped ', INumber, ' times.');
End.  {Hovedalgoritme}

{*********************************************}

If possible, pls send the reply by e-mail as well as posting it.
Fredrik

=======================================================
"640k should be enough for anybody" - Bill Gates, 1981.

Fredrik Endresen
Po.box 206             Voice: (+47) 75 05 68 17
N-8700 Nesna           e-mail:  f...@nord.eunet.no
=======================================================

## Re:URGENT ** Problem with Iteration ** URGENT

##### Quote
f...@nord.eunet.no (Fredrik Endresen) wrote:
>The program is to make a list of numbers, write them to screen, ask
>the user for a number and check the list if the number is there. The
>checking should work both with recursion and iteration. The recursion
>works every time, but the iteration routine rapports that the number
>does not exist if it exists. This happens at more or less regular
>intervals.

[snip...]

##### Quote
>Procedure FindNumberI(NumberList:Table;L, R, x:Integer; Var
>INumber:Integer);

>Var
>   m : Integer;

>Begin
>   INumber := 0;
>   While (L < R) do
>      Begin {while}
>         INumber := INumber + 1;
>         m := (L + R) div 2;
>         If NumberList[m] < x then
>            L := m + 1
>         Else
>            R := m;
>      End;  {while}
>      If NumberList[m] = x then

Opps, when the loop has ended you should test

If NumberList[R] = x Then ...

When L is one less than R and the last test comes in low, then L becomes m+1
breaking the loop.  "m" in this situation is below the "ending" position. If you
study this a little you should see that the ending entry is not m, but r.

...red
cc

- Show quoted text -

##### Quote
>         Writeln('The number ', x, ' exists')
>      Else
>         Writeln('The number ', x, ' does not exist');
>End;