Recursive Functions and Debugging (Solving Problems in Computer Science, ATypical CompSci)

recursive_debug.re

let directSumFrom1To = (n: int): int => n * (n + 1) / 2;
let directSumFrom1To: int => int = n => n * (n + 1) / 2;
let directSumFrom1To = n => n * (n + 1) / 2;

/* Step 1 */
/*
 * let choose_from = (k, n) =>
 *   choose_from(k - 1, n - 1) + choose_from(k, n - 1);
 */

/* Step 2 */
let rec choose_from = (k, n) =>
  choose_from(k - 1, n - 1) + choose_from(k, n - 1);

/* Step 3 */
let rec choose_from = (k, n) =>
  if (k == 0 || k == n) {
    1;
  } else {
    choose_from(k - 1, n - 1) + choose_from(k, n - 1);
  };

/* More concisely */
let rec choose_from = (k, n) =>
  k == 0 || k == n ? 1 : choose_from(k - 1, n - 1) + choose_from(k, n - 1);

/* To see code working in action */
let generate = (f, n) => {
  let rec loop = k => k == n ? [] : [f(k), ...loop(k + 1)];
  loop(0);
};

let row = n => generate(x => (x, n), n + 1);

let pascalUptoRow = n =>
  generate(n => List.map(((x, y)) => choose_from(x, y), row(n)), n + 1);

/* Debugging 1 */
let rec choose_debug = (k, n) => {
  Printf.printf("(%d,%d)\n", k, n);
  choose_debug(k - 1, n - 1) + choose_debug(k, n - 1);
};

/* Debugging 2 */
let rec choose_debug = (k, n) => {
  let result = choose_debug(k - 1, n - 1) + choose_debug(k, n - 1);
  Printf.printf("(%d,%d)\n", k, n);
  result;
};

/* Debugging 3 */
let untied_choose = (recurse_on, k, n) =>
  k == 0 || k == n ? 1 : recurse_on(k - 1, n - 1) + recurse_on(k, n - 1);

/* Debugging 4 */
let rec choose_from = (k, n) => untied_choose(choose_from, k, n);

let rec choose_debug = (k, n) => {
  Printf.printf("(%d,%d)\n", k, n);
  untied_choose(choose_debug, k, n);
};

/* Less useful... */
let rec choose_debug2 = (k, n) => {
  let result = untied_choose(choose_debug2, k, n);
  Printf.printf("(%d,%d)\n", k, n);
  result;
};