Как передать значения при преобразовании рекурсивной функции в итеративную со стеком и циклом while

Вы можете передавать значения, используя словарь, в котором хранится параметр вызова рекурсивной функции. См. комментарии в приведенном ниже коде, которые, надеюсь, ответят на заданные вами вопросы:

def recursive_travel(l, r, cur_height, max_height):
    def f(l,r):
        return l+r
    if cur_height == max_height:
       return f(l, r) * (f(l+1, r) + f(l, r+1))
    return recursive_travel(l+1, r, cur_height+1, max_height) + recursive_travel(l, r+1, cur_height+1, max_height)
    
def stack_travel(l, r, min_height, max_height):
    # Define the function f
    def f(l, r):
        return l + r

    # Stack to hold states to process
    stack = [(l, r, min_height)]
    results = {}  # Dictionary to store the results of subproblems

    # Process until the stack is empty
    while stack:
        cur_l, cur_r, cur_height = stack.pop()

        # Calculate base case directly
        if cur_height == max_height:
            if (cur_l, cur_r, cur_height) not in results:
                results[(cur_l, cur_r, cur_height)] = f(cur_l, cur_r) * (f(cur_l + 1, cur_r) + f(cur_l, cur_r + 1))
        else:
            # Check if children results are ready
            left_key = (cur_l + 1, cur_r, cur_height + 1)
            right_key = (cur_l, cur_r + 1, cur_height + 1)

            # Calculate if children are already processed
            if left_key in results and right_key in results:
                results[(cur_l, cur_r, cur_height)] = results[left_key] + results[right_key]
            else:
                # Re-add current node to process later
                stack.append((cur_l, cur_r, cur_height))
                # Ensure children are in the stack to be processed
                if left_key not in results:
                    stack.append(left_key)
                if right_key not in results:
                    stack.append(right_key)

    # Return the result for the initial call
    return results[(l, r, min_height)]

# Test the function
print(recursive_travel(1, 2, 3, 4))
print(stack_travel(1, 2, 3, 4))
print(recursive_travel(5, 6, 7, 8))
print(stack_travel(5, 6, 7, 8))

Что дает в качестве вывода:

80
80
624
624

предполагая, что версия стека работает должным образом.

ОБНОВЛЕНИЕ с учетом измененной рекурсивной функции:

def recursive_travel(l, r, cur_height, max_height):
    def f(l, r):
        return l*r*(l + r)
    if cur_height == max_height - 1:
        return f(l, r) * (f(l+1, r) + f(l, r+1))
    return f(l,r)* (recursive_travel(l+1, r, cur_height+1, max_height) + recursive_travel(l, r+1, cur_height+1, max_height))

def stack_travel(l, r, min_height, max_height):
    # Define the function f
    def f(l, r):
        return l*r*(l + r)

    # Stack to hold states to process
    stack = [(l, r, min_height)]
    results = {}  # Dictionary to store the results of subproblems

    # Process until the stack is empty
    while stack:
        cur_l, cur_r, cur_height = stack.pop()

        # Calculate base case directly when cur_height is max_height - 1
        if cur_height == max_height - 1:
            if (cur_l, cur_r, cur_height) not in results:
                results[(cur_l, cur_r, cur_height)] = f(cur_l, cur_r) * (f(cur_l + 1, cur_r) + f(cur_l, cur_r + 1))
        else:
            # Check if children results are ready
            left_key = (cur_l + 1, cur_r, cur_height + 1)
            right_key = (cur_l, cur_r + 1, cur_height + 1)

            # Calculate if children are already processed
            if left_key in results and right_key in results:
                # Multiply the sum of children results by f(cur_l, cur_r)
                results[(cur_l, cur_r, cur_height)] = f(cur_l, cur_r) * (results[left_key] + results[right_key])
            else:
                # Re-add current node to process later
                stack.append((cur_l, cur_r, cur_height))
                # Ensure children are in the stack to be processed
                if left_key not in results:
                    stack.append(left_key)
                if right_key not in results:
                    stack.append(right_key)

    # Return the result for the initial call
    return results[(l, r, min_height)]

Для полноты картины ниже функция, предоставляемая тринкотом, адаптирована для приема начального параметра l, r, min_height, max_heigt:

def get_left_right( l , r , path_len , path):
    right = path.bit_count() # Number of times we go right on this path
    left = path_len - right # Number of times we go left on this path
    return l + left, r + right

def iterative_travel( l , r , min_height , max_height):
    def f(l, r):
        return l*r*(l + r)
    level = [0, 1] * ( 2 << ( max_height - min_height ) )
    for depth in range(((max_height  - 1) - min_height  + 1) , -1, -1):
        level = [
            f( *get_left_right(l, r, depth, path) ) * (level[path*2] + level[path*2+1]) 
            for path in range(1 << depth)
        ]
        #print(level)
    return level[0]

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

База рекурсии по-прежнему учитывает один дополнительный уровень виртуального дерева, поскольку вызывает f с увеличенным аргументом. Поэтому я бы переписал рекурсивную функцию, используя базовый вариант на один уровень глубже:

def recursive_travel(l, r, cur_height, max_height):
    if cur_height == max_height + 1:
        return f(l, r)
    return f(l, r) * (recursive_travel(l + 1, r, cur_height + 1, max_height)
                    + recursive_travel(l, r + 1, cur_height + 1, max_height))

Это лучше показывает, как каждый узел вносит свой «собственный» вклад (определяемый f). Это означает, что виртуальное двоичное дерево на самом деле находится на один уровень выше, чем max_height.

Другое наблюдение заключается в том, что l и r обозначают количество левых и правых поворотов на пути от корня к узлу. Это означает, что поддерево, имеющее те же номера l и r, что и другое поддерево, получит точно такое же значение. Было бы напрасной тратой пересчитывать все это поддерево более одного раза.

Таким образом, ваше дерево на самом деле представляет собой скорее сеть, которая выглядит следующим образом:

                /\
               //\
              ///\
             ////\
            /////\ 
           //////\
          ... ... ... ...

Это уменьшает количество узлов, которые вам фактически нужно оценить, делая количество вычислений O(𝑛²) вместо O(2^𝑛).

Мы могли бы превратить это в итеративное решение восходящим способом: сначала вычислить результат для всех уникальных комбинаций l-r внизу, затем для всех родительских комбинаций... до тех пор, пока не будет определено значение корня, которое также является конечный результат.

Объединив все эти наблюдения, мы получаем этот код:

def iterative_travel(max_height):
    level = [
        f(left, max_height + 1 - left)
        for left in range(max_height + 2)
    ]
    for height in range(max_height, -1, -1):
        for left in range(height + 1):
            level[left] = f(left, height - left) * (level[left] + level[left + 1])
    return level[0]

Эффективность

С вашим рекурсивным подходом не должно быть слишком большой разницы при условии, что вы применяете мемоизацию. Это можно сделать, например, с помощью functools.cache.

Например, я придумал простой f и запустил максимальную высоту 100:

from functools import cache

def f(l, r):
    return 2 + l * 3 + r * 5  # Some example calculation

@cache
def recursive_travel(l, r, cur_height, max_height):
    if cur_height == max_height + 1:
        return f(l, r)
    return f(l, r) * (recursive_travel(l + 1, r, cur_height + 1, max_height)
                    + recursive_travel(l, r + 1, cur_height + 1, max_height))

def iterative_travel(max_height):
    level = [
        f(left, max_height + 1 - left)
        for left in range(max_height + 2)
    ]
    for height in range(max_height, -1, -1):
        for left in range(height + 1):
            level[left] = f(left, height - left) * (level[left] + level[left + 1])
    return level[0]

n = 100
result = recursive_travel(0, 0, 0, n)
print(result)
result2 = iterative_travel(n)
print(result2)

Этот скрипт печатает результат за долю секунды для обоих подходов. Для больших высот, например 300, итеративная версия оказывается быстрее, но обе по-прежнему завершаются менее чем за 1 секунду.