Не понимаю отдельный этап выполнения программы с рекурсией

Question

Есть программа, которая на основе представленного числа, в нашем примере число 13, пытается создать для него выражение (((1 * 3) + 5) + 5). При дебагинге программы наступает момент, когда выражение a || b возвращает null и выражение из промежуточного (((1 + 5) + 5) * 3) становится становится (1 + 5).

Пожалуйста, кому не сложно, прогоните функцию в дебагинге и расскажите как так получается.

 function findSolution(target)
    {
        function find(current, history) // 1 "1" // 6 "(1 + 5)" // 11 "((1 + 5) + 5)" // 16 NULL
                                       // 33 "((1 + 5) + 5)" NULL
        {
            if(current == target)
                return history;
            else if(current > target)
                return null;
            else
            {
                return find(current + 5,`(${history} + 5)`) ||
                       find(current * 3,`(${history} * 3)`);
            }
        }
        return find(1, "1");
    }

Answer 1

 return find(current + 5,`(${history} + 5)`) ||
                       find(current * 3,`(${history} * 3)`);

У вас тут логическая ошибка - вы все время идете по ветке +5, пока не упретесь в условие. Тогда вы возвращаетесь и пробуете *3, но если и там null - он и возвращается. Функция не может вернутся на несколько шагов и попробовать другой вариант, если через несколько вызовов окажется, что он не подходит. Мне задача показалась интересной и я сделал свой вариант решения:

const findSolution = (function (){
  const tree = [1]; /*
    3,              6,
    9,      8,      18,     11,
    27, 14, 24, 13, 54, 23, 33, 16
  ];
  */
  const itol = i => {
    let lvl = 0, n = 0;
    while(n < i) n += 2 << lvl++;
    return lvl;
  }
  const ltoi = l => 2 ** l - 1;
  const parent = i => {
    const lvl = itol(i);
    const pos = i - ltoi(lvl);
    return ltoi(lvl - 1) + (pos >>> 1)
  }
  const grow = () => {
      const lvl = itol(tree.length);
      for(let i = tree.length; i < ltoi(lvl + 1); i++) tree.push((i%2) ? tree[parent(i)] * 3 : tree[parent(i)] + 5);
  }
  const tostr = (history, str = "1") => history.length ? tostr(history, (history.pop() ? `(${str} * 3)` : `(${str} + 5)`)) : str;
  const find = (target, history = []) => {
    if(target === 1) return tostr(history);
    while(Math.max(target, ...tree) == target) grow();
    const i = tree.findIndex(el => el == target);
    if(!~i) return null;
    history.push(i % 2);
    return find(tree[parent(i)], history);
  };
  return find;
})();

<input oninput="console.log(findSolution(this.value))" />

Он тоже далек от идеала, в частности правильное условие для роста дерева мне придумать не удалось. Чтобы найти разложение для, например, числа 36 (7 раз + 5, 7ой уровень дерева), нужно сначала забить число больше 1458, т.к. оно на 6ом уровне: ((((((1 + 5) * 3) * 3) * 3) * 3) * 3)

БЛОГ НА HUSL

Не понимаю отдельный этап выполнения программы с рекурсией

Ответы (1 шт):