######################## PROBLÈME 4: #########################

#@# a)
fact := proc(n)
  n * fact(n-1);
end;
fact(0) := 1;

fact2 := proc(n)
  local i,N;
  N := 1;
  for i from 2 to n do
    N := N*i
  od;
  N;
end;

#@# b)

#@# multiplication des éléments d'une liste par "divide and conquer"
#@# 1ère version
mymul := proc(L)
  local i, x, k, lx; #@# x = liste des éléments a multiplier
                     #@# lx= nombre d'éléments de x
  lx := nops(L);
  if   (lx = 0) then RETURN(1);
  elif (lx = 1) then RETURN(L[1]);
  fi;
  x := array(L); #@# copie locale. Ses éléments sont remplacés par
                 #@# les produits 2 a 2 successifs (array car une liste
                 #@# serait inefficace)
  k := lx;
  while (k > 1) do
    lx := k; k := 0;
    for i to lx-1 by 2 do
      k := k+1;
      x[k] := x[i] * x[i+1];
    od;
    if (i = lx) then
      k := k+1;
      x[k] := x[i];
    fi
  od;
  x[1];
end;

#@# c)
#@# 2eme version:
mymul2 := proc(L)
  local i, x, k, lx; #@# x = liste des elements a multiplier
                     #@# lx= nombre d'elements de x
  lx := nops(L);
  if   (lx = 0) then RETURN(1);
  elif (lx = 1) then RETURN(L[1]);
  fi;
  x := array(L);
  k := lx;
  while (k > 1) do
    lx := k; k := 0;
    for i to lx/2 do
      k := k+1;
      x[k] := x[i] * x[lx+1-i];
    od;
    if (i = (lx+1)/2) then
      k := k+1;
      x[k] := x[i];
    fi
  od;
  x[1];
end;

#@# d)
myfact := n -> mymul( [ seq(i, i=1..n) ] );

#@# légèrement plus rapide (produits plus équilibrés)
myfact2 := n -> mymul2( [ seq(i, i=1..n) ] );