let rec recurse n z f =
  if n = 0 then z
  else f n (recurse (n - 1) z f)

(* 1. Intervalle [n; n-1; ...; 1]  (naturellement décroissant) *)
let range_dec n = recurse n [] (fun k acc -> k :: acc)
(* range_dec 4 = [4; 3; 2; 1] *)

(* 2. Intervalle [1; 2; ...; n]  (croissant par reverse) *)
let range n = List.rev (recurse n [] (fun k acc -> k :: acc))
(* range 4 = [1; 2; 3; 4] *)

(* 3. n copies d'une valeur *)
let replique n x = recurse n [] (fun _ acc -> x :: acc)
(* replique 5 0 = [0; 0; 0; 0; 0] *)

(* 4. Carrés : [n²; ...; 1²] *)
let carres n = recurse n [] (fun k acc -> k * k :: acc)
(* carres 5 = [25; 16; 9; 4; 1] *)

(* 5. Premiers entiers pairs ≤ n, ordre décroissant *)
let pairs n = recurse n [] (fun k acc -> if k mod 2 = 0 then k :: acc else acc)
(* pairs 10 = [10; 8; 6; 4; 2] *)

(* 6. Puissances de 2 : [2^n; 2^{n-1}; ...; 2^0] *)
let puiss2 n = recurse n [] (fun k acc -> (1 lsl k) :: acc)
(* puiss2 4 = [16; 8; 4; 2]  -- note : n=0 donne [], donc 2^0 est absent *)

(* 7. n premiers multiples de m, ordre croissant *)
let multiples m n = List.rev (recurse n [] (fun k acc -> m * k :: acc))
(* multiples 7 5 = [7; 14; 21; 28; 35] *)

(* 8. Liste de factorielles [1!; 2!; ...; n!] *)
let factorielles n =
  let (_, lst) = recurse n (1, []) (fun k (fact, acc) ->
    let fact' = fact * k in
    (fact', fact' :: acc))
  in
  List.rev lst
(* factorielles 5 = [1; 2; 6; 24; 120] *)

(* 9. n premiers nombres de Fibonacci (ordre croissant) *)
let fibonacci n =
  let (_, lst) = recurse n ((0, 1), []) (fun _ ((a, b), acc) ->
    let c = a + b in
    ((b, c), c :: acc))
  in
  List.rev lst
(* fibonacci 8 = [1; 2; 3; 5; 8; 13; 21; 34] *)

(* 10. Crible : liste des entiers ≤ n qui passent un prédicat *)
let filtre n p = List.rev (recurse n [] (fun k acc -> if p k then k :: acc else acc))
(* filtre 20 (fun k -> k mod 3 = 0) = [3; 6; 9; 12; 15; 18] *)

(* 11. Scan : accumule les résultats intermédiaires d'une opération binaire
       scan (⊗) n init = [init; 1⊗init; 2⊗1⊗init; ...; n⊗...⊗1⊗init] *)
let scan n init op =
  let (_, lst) = recurse n (init, [init]) (fun k (acc, hist) ->
    let acc' = op k acc in
    (acc', acc' :: hist))
  in
  List.rev lst
(* scan 5 0 (+) = [0; 1; 3; 6; 10; 15] *)
(* scan 5 1 ( * ) = [1; 1; 2; 6; 24; 120] *)

let () =
  Printf.printf "range_dec 4    = [%s]\n" (String.concat "; " (List.map string_of_int (range_dec 4)));
  Printf.printf "range 4        = [%s]\n" (String.concat "; " (List.map string_of_int (range 4)));
  Printf.printf "replique 5 0   = [%s]\n" (String.concat "; " (List.map string_of_int (replique 5 0)));
  Printf.printf "carres 5       = [%s]\n" (String.concat "; " (List.map string_of_int (carres 5)));
  Printf.printf "pairs 10       = [%s]\n" (String.concat "; " (List.map string_of_int (pairs 10)));
  Printf.printf "puiss2 4       = [%s]\n" (String.concat "; " (List.map string_of_int (puiss2 4)));
  Printf.printf "multiples 7 5  = [%s]\n" (String.concat "; " (List.map string_of_int (multiples 7 5)));
  Printf.printf "factorielles 5 = [%s]\n" (String.concat "; " (List.map string_of_int (factorielles 5)));
  Printf.printf "fibonacci 8    = [%s]\n" (String.concat "; " (List.map string_of_int (fibonacci 8)));
  Printf.printf "filtre 20 mod3 = [%s]\n" (String.concat "; " (List.map string_of_int (filtre 20 (fun k -> k mod 3 = 0))));
  Printf.printf "scan 5 0 (+)   = [%s]\n" (String.concat "; " (List.map string_of_int (scan 5 0 (+))));
  Printf.printf "scan 5 1 ( * ) = [%s]\n" (String.concat "; " (List.map string_of_int (scan 5 1 ( * ))))