View original (French)

Lcm with recursion

Solved/Closed
AMOULA_info -  
Bonjour,
Hello everyone
I would like to know how to calculate the lcm(a,b) using the recursive method in Pascal without adding another parameter to the function header, knowing that I know the iterative method with two ways:
1st method:
function lcm(a,b: integer):integer;
var i :integer;
begin
i:=1;
if a*b = 0 then lcm :=0 else
begin
while a*i mod b <> 0 do
i:=i+1;
lcm:=a*i;
end;
end;
2nd method:
function lcm(a,b: integer):integer;
var max,min :integer;
begin
if a*b = 0 then lcm :=0 else
begin
if a>b then begin max :=a; min:=b ; end
else begin max :=b; min :=a; end;
while max mod min <> 0 do
max := max +(a+b-min);
lcm:=max;
end;
end;

Thank you for your help
Configuration: Windows XP Internet Explorer 6.0

9 answers

  1. malibous
    I present to you the complete solution of the entire program that calculates the LCM (Least Common Multiple) of two integers a and b using the recursive method while respecting the constraints for inputting a and b:

    program lcm_rec;
    uses wincrt;
    var
    a,b:word;

    procedure input(var a,b:word);
    begin
    repeat
    writeln('enter a: ');
    readln(a);
    writeln('enter b: ');
    readln(b);
    until ((a>b) and (a>0));
    end;

    function lcm(a,b:word): longint;

    var
    r:integer;

    begin
    if (b = 0) then
    lcm := 0
    else if (a mod b = 0) then
    lcm := a
    else
    begin
    r:=a mod b;
    lcm:=( a div r)* lcm(b,r);
    end;
    end;

    begin
    input(a,b);
    writeln('the lcm of ',a,' and ',b,' is ',lcm(a,b));
    end.
    8
    1. rouna10
      ```html function ppcm(a,b:word): longint;

      var
      r:integer;

      begin
      if (b = 0) then
      ppcm := 0
      else if (a mod b = 0) then
      ppcm := a
      else
      ppcm:=( a div (a mod b))* ppcm(a,a mod b);
      end; ```
      0
    2. rouna10
      If you run your program with integers a and b (for example a=23 and b=5) you found a false result.
      You need to replace "ppcm:=( a div r)* ppcm(b,r);" with "ppcm:=( a div r)* ppcm(a,r);"
      0
    3. rouna10
      ```html

      Write this same algorithm without using any function or procedure.

      ```
      0
    4. Sahar
      Thank you
      0
    5. lido
      this result is wrong... it is necessary to replace ppcm:=(a div r)*ppcm(b,r); with ppcm:=ppcm(b,r)*(a div r); and it is not the same thing.
      0
  2. AMOULA_info Author
    Thank you all, I found the solution myself!!!

    function lcm(a,b:integer) : integer;
    var r : integer;
    begin

    if a mod b = 0 then lcm := a

    else

    begin
    r:=a mod b;
    lcm:=( a div r)* lcm(b,r);
    end;

    end;
    1
    1. dali
      Hello
      with all my respect for your point of view, regarding this solution (it's a good solution); but it lacks the division by zero test :) that is to say if the second parameter is equal to zero then the solution is incorrect (run time error) :) . okay?
      0
    2. amoula_info
      @daliThank you for your interest and especially for your politeness, but it is enough to add another test at the beginning to solve this problem.
      function ppcm(a,b:integer) : integer;
      var r : integer;
      begin

      if b = 0 then ppcm := 0
      else if a mod b = 0 then ppcm := a

      else

      begin
      r:=a mod b;
      ppcm:=( a div r)* ppcm(b,r);
      end;

      end;
      my real problem was with parameters making the new call to the function.
      and here is how I found the solution.
      ppcm(a,b)* pgcd(a,b) = a*b {mathematical theorem}
      hence pgcd(a,b ) = (a*b) / ppcm(a,b)
      and since pgcd(a,b) = pgcd(b,r) {with r = a mod b} and pgcd (b,r) = (b*r)/ ppcm(b,r) {} according to the previous theorem}
      we can conclude that (a*b) / ppcm(a,b) = (b*r) / ppcm(b,r) hence ppcm(a,b) =( (a*b)/ (b*r))*ppcm(b,r)
      = (a div r )*ppcm(b,r)
      I hope I was clear enough
      0
    4. fenni
      Here is an optimal solution:

      Function ppcm (a, b, r : integer) : integer;
      begin
      if (r mod b)=0
      then ppcm := r
      else ppcm := ppcm (a, b, r+a) ;
      end;
      The call will be: Writeln ('PPCM = ', ppcm(a,b,a));
      0
  3. Ouhiby
    Function ppcmRec1 (a,b,i :integer):integer;
    begin
    if a * b = 0 then
    ppcmR := 0
    else
    if a * i mod b = 0 then
    ppcmR := a * i
    else
    ppcmR := ppcmRec1(a,b,i+1);
    End;

    Call X :=ppcmRec1(a,b,1)
    1
    1. Ouhiby
      Sorry, I made some call errors :)
      Here is the complete solution InShaAllah

      Program testppcm ;
      uses wincrt;

      function ppcm1(a,b: integer):integer;
      var i :integer;
      begin
      i:=1;
      if a*b = 0 then
      ppcm1 :=0
      else
      begin
      while a*i mod b <> 0 do
      i:=i+1;
      ppcm1:=a*i;
      end;
      end;

      Function ppcmRec1 (a,b,i :integer):integer;
      begin
      if a * b = 0 then
      ppcmRec1 := 0
      else
      if a * i mod b = 0 then
      ppcmRec1 := a * i
      else
      ppcmRec1 := ppcmRec1(a,b,i+1);
      End;

      function ppcm2(a,b: integer):integer;
      var max,min :integer;
      begin
      if a*b = 0 then
      ppcm2 :=0
      else
      begin
      if a>b then
      begin
      max :=a;
      min:=b ;
      end
      else
      begin
      max :=b;
      min :=a;
      end;
      while max mod min <> 0 do
      max := max +(a+b-min);
      ppcm2:=max;
      end;
      end;

      function ppcmRec2(a,b: integer):integer;
      Var
      max,min : integer;
      Begin

      if a*b = 0 then
      ppcmRec2 :=0
      else
      begin
      if a>b then
      begin
      max :=a;
      min:=b ;
      end
      else
      begin
      max :=b;
      min :=a;
      end;
      if max mod min = 0 then
      ppcmRec2:=max
      else
      ppcmRec2 := ppcmRec2(max +(a+b-min),b);

      end;

      End;

      Begin
      {example of call}
      Writeln(ppcm1(15,3));
      Writeln(ppcmRec1(3,15,1));
      Writeln(ppcm2(4,12));
      Writeln(ppcmRec2(23,42));

      {
      Result :
      15
      15
      12
      84
      }
      End.
      0
      2. amoula_info
        Hi Ouhiby,
        for the recursive function ppcmrec2, I think (and I've tested it actually) that it is incorrect.
        1
        1. Ouhiby
          Oh yes, I couldn't correct it!!!
          What do you think?
          0
      3. lkj
        I found several solutions
        but which one is the most accurate
        please
        very urgent!!!!!!!!!!!
        1
        1. rouna10
          ```pascal function ppcm(a,b:word): longint;

          var
          r:integer;

          begin
          if (b = 0) then
          ppcm := 0
          else if (a mod b = 0) then
          ppcm := a
          else
          ppcm:=( a div (a mod b))* ppcm(a,a mod b);
          end;

          { it is the most just } ```
          0
      4. rihab chebbah
        Désolé, je ne peux pas vous aider.
        1
        1. Malebete
          Astonishing the number of algorithms proposed that assume a >= b ;)

          Test them with lcm(1, 53), or even lcm(0, 22) ;))
          1
          1. dorsaf007
            ```pascal Function lcm (a,b:integer):integer;
            begin
            if a=b then lcm:=a
            else if a>b
            then lcm:=(lcm(a-b,b)*a) div (a-b)
            else lcm:=(lcm(a,b-a)*b) div (b-a);
            end; ```
            1