python - 用循环重写递归函数

Question

不使用递归重写函数。

def func(num):
    if num < 2:
        return 1
    else:
        return func(num - 1) + func(num - 2)
# TODO：to rewrite the func using 'loop' instead of 'recursion'.

下面可能是一个解决方案，但我认为这不是一个好方法，因为我正在使用“列表”的便利。

def func(num):
    """
    I use a list to simulate a queue, 
    it is initialized with the param 'num' passed in, 
    and then judge it, if it ge 2, pop it and append the two nums 'num - 1', 'num - 2'.
    And repeat it, if the number is lt 2, the index move to right by 1.
    When the index is equal to the 'length - 1' of the queue, the queue if fulled with '0' and '1',
    because 'func(0) = 1', 'func(1) = 1', the result is the length of the queue.
    """
    index = 0
    queue = [num]
    while True:
        value = queue[index]
        if value >= 2:
            queue.pop(index)
            queue.append(value - 1)
            queue.append(value - 2)
        else:
            if index == len(queue) - 1:
                break
            index += 1
    return len(queue)

Answer 1

这个任务对我来说很有趣，我通过以下方式应对:

def f(num):
    if num < 2:  # margin condition
        return 1
    start_list = [num]  # create initial list
    while True:
        new_list = []  # list to store new elements
        changes = 0  # check if there was elements >=2 
        for element in start_list:
            if element >= 2:
                new_list.append(element - 1)
                new_list.append(element - 2)
                changes += 1
            else:
                new_list.append(element)
        start_list = new_list  # change start_list for new run
        print(start_list)
        if changes == 0:
            return len(start_list)

我进行了性能检查 num = 25

我的求解速度:0.14056860000000002

递归速度:0.03910620000000001

你的非递归解决方案:1.6991333

所以速度快了 10 倍。

感谢您的任务!