Alexandroppolus

www.tvd-home.ru/recursion

40000000 чисел Фибоначчи - это лютая вещь со всех сторон. Даже если ты врубишь мемоизацию, как посоветовал Максим Припадчев , то там дохрена вычислений, потому что числа будут длиной в миллионы цифр.

Мы суммируем только четные числа Фибоначчи.
Легко заметить, что F(n) четное, только если n делится на 3, т.е. n = 3m.
То есть тебе нужна сумма F(3*m) для всех m от 0 до floor((40000000-2) / 3) включительно, если правильно понимаю этот ваш range.

я тут пояндексил и промыслил формулы:
1) F(3*n) = F(n+1)^3 + F(n)^3 + F(n-1)^3 (из википедии)
2) sum[0...N] F(i)^3 = (1/2)*(F(n)*F(n+1)^2 + (-1)^(n-1)*F(n-1) + 1) отсюда

сумму F(3*n) можно выразить через сумму F(n)^3 и потом применить формулу (2)

в итоге получается

sum[0...N] F(3*i) = (1/2)*(F(n)*F(n+1)^2 + (-1)^(n-1)*F(n-1) + 1) - 1 + F(n)^3 + F(n+1)^3

для этого выражения нам нужны F(n), F(n+1) и F(n-1) = F(n+1) - F(n)

F(n) и F(n+1) вычисляем методом "fast doubling", который делает O(ln(n)) действий вместо O(n) стандартного способа. Ускорение знатное.

Итого:

const fib = (n, a = []) => {
    if (n < 1) {
        a[0] = 0n;
        a[1] = 1n;
    } else {
        const m = Math.floor(n/2);
        fib(m, a);
        const x = a[0] * (2n * a[1] - a[0]);
        const y = a[0] * a[0] + a[1] * a[1];
        if (n % 2) {
            a[0] = y;
            a[1] = x + y;
        } else {
            a[0] = x;
            a[1] = y;
        }
        
    }
    return a;
}

const sumFib3n = (n) => {
    if (n < 1) { return 0n; }

    const [fn, fnp1] = fib(n); // fn = fib(n), fnp1 = fib(n+1), 
    const fnm1 = fnp1 - fn;  // fnm1 = fib(n-1), 
    const sgn = n % 2 ? 1n : -1n;
    const sumPow3 = (fn * fnp1 * fnp1 + sgn * fnm1 + 1n) / 2n;
    
    return sumPow3 - 1n + fn * fn * fn + fnp1 * fnp1 * fnp1;
}

console.log(sumFib3n(Math.floor((40000000 - 2)/3)));

function getIntermediateItems(tree, result = []) {
  tree?.forEach((item) => {
    if (item.workControl?.includes('intermediate')) {
      result.push(item);
    }
    getIntermediateItems(item.content, result);
  });
  return result;
}

const arr = getIntermediateItems(myarr);
document.getElementById("dd").prepend(JSON.stringify(arr, '', 4))

Сейчас код выводит только половину

ну так дорисуй вторую половину

...
return str(n) * m + '\n' + print_pattern(n - 1, m - n) + '\n' + print_pattern(n - 1, m - n) + '\n' + str(n) * m

Не помню паскалевского синтаксиса, но как-то так:

function f(n: integer): integer;
var a, b, c: integer;
begin
  if n < 2
  then f:= -2
  else if n = 2
  then f:= 2
  else
  begin
     a := -2;
     b := 2;
     for i = 3...n begin
        c := b;
        b := 3*b - a;
        a := c;
     end;
     f:= b;
   end;
end;

Как видим, рекурсия тут без надобности

Что у тебя там за дерево?
Например, если это сбалансированное двоичное дерево, то можно использовать подход как здесь
Если что-то другое, то надо смотреть, что именно.

int Min(int arr[], int n, int current) {
  return n > 0 ? Min(arr, n - 1, min(current, arr[n-1])) : current;
}


int minValue = Min(arr, n, +бесконечность)

ещё вариант

int Min(int arr[], int n) {
  return n > 0 ? min(Min(arr, n - 1), arr[n-1])) : +бесконечность;
}


int minValue = Min(arr, n);

Однако первый способ хорош тем, что там хвостовая рекурсия, и компилятор теоретически может развернуть её в цикл.

Если внутри функции делается несколько рекурсивных вызовов, то вариант цикл+стек будет смотреться сложно и вышеупомянутые джуны ощутят трудности его понимания. Или, например, кейс, когда есть взаимная рекурсия двух или более функций - там придется код как-то перекроить, смотря по ситуации.

Нерекурсивный вариант обязательно следует использовать, когда можно обойтись без стека, как в избитом примере вычисления факториала. Так же - когда существует ненулевая вероятность, что будет переполнение стека: например, функция работает с произвольным двоичным деревом, и может получить на вход очень сильно несбалансированное дерево большой высоты. Ещё есть разные специальные кейсы. Допустим, обход графа в глубину: если сделать его нерекурсивным, то можно будет легко заменить в функции стек на очередь и получить обход в ширину, или даже на приоритетную очередь, тогда будет "поиск по критерию стоимости"

Кейс, где рекурсивный вызов - самое последнее действие функции, это "хвостовая рекурсия". В некоторых языках и средах выполнения имеет место "оптимизация хвостовой рекурсии", то есть компилятор переписывает это дело так, что текущий вызов завершается перед следующим, и таким образом не будет переполнения стека, какой бы глубокой рекурсия ни была.
В языках программирования, куда не завезли цикл, это имеет смысл. В нормальных ЯП такая фича бесполезна, потому что легко переделать на цикл вручную. Есть ли оно в Питоне, непонятно, беглый поиск ответа не дал.