let rec recurse : 'a. int -> 'a -> (int -> 'a -> 'a) -> 'a =
  fun n z f -> if n = 0 then z else f n (recurse (n - 1) z f)

(* 1. Somme des n premiers entiers *)
let somme n = recurse n 0 (+)
(* somme 5 = 15 *)

(* 2. Puissance : x^n *)
let puissance x n = recurse n 1 (fun _ acc -> x * acc)
(* puissance 2 10 = 1024 *)

(* 3. Factorielle double : n!! = n * (n-2) * (n-4) * ... *)
let factorielle_double n = recurse n 1 (fun k acc -> if k mod 2 = n mod 2 then k * acc else acc)
(* factorielle_double 6 = 6*4*2 = 48, factorielle_double 5 = 5*3*1 = 15 *)

(* 4. Fibonacci : (F_n, F_{n+1}) *)
let fib_pair n = recurse n (0, 1) (fun _ (a, b) -> (b, a + b))
let fib n = fst (fib_pair n)
(* fib 10 = 55 *)

(* 5. Produit scalaire de deux vecteurs représentés par leur longueur
      et une fonction d'accès : <v, w> = sum_{i=1}^{n} v_i * w_i *)
let produit_scalaire n v w = recurse n 0 (fun i acc -> v i * w i + acc)
(* exemple : let v i = i and w i = 2*i in produit_scalaire 3 v w = 1*2 + 2*4 + 3*6 = 28 *)

(* 6. Horner : évaluation polynomiale P(x) = a_n * x^n + ... + a_1 * x + a_0
      donné par une fonction a: i -> a_i (où a_i est le coefficient de degré i) *)
let horner n x a = recurse n 0 (fun i acc -> a i + x * acc)
(* a(0) + x*(a(1) + x*(a(2) + ...)) *)

(* 7. Dénombrement : nombre de parties d'un ensemble à n éléments = 2^n *)
let parties n = recurse n 1 (fun _ acc -> 2 * acc)
(* parties 4 = 16 *)

(* 8. Approximation de exp(1) par la série de Taylor : sum_{k=0}^{n} 1/k! *)
let rec fact k = if k <= 1 then 1 else k * fact (k - 1)

let e_approx n =
  1.0 +. recurse n 0.0 (fun k acc -> acc +. 1.0 /. float_of_int (fact k))
(* e_approx 10 ≈ 2.7182818011 *)

(* 9. Accumulateur générique : rebondit n fois sur une fonction d'état *)
let rebond n init f = recurse n init (fun _ s -> f s)
(* rebond 3 0 (fun x -> x + 1) = 3 *)

let () =
  Printf.printf "somme 5 = %d\n" (somme 5);
  Printf.printf "puissance 2 10 = %d\n" (puissance 2 10);
  Printf.printf "factorielle_double 6 = %d\n" (factorielle_double 6);
  Printf.printf "fib 10 = %d\n" (fib 10);
  Printf.printf "parties 4 = %d\n" (parties 4);
  Printf.printf "e_approx 10 = %.10f\n" (e_approx 10);
  Printf.printf "rebond 3 0 (fun x -> x + 1) = %d\n" (rebond 3 0 (fun x -> x + 1))