Блог

Главная - Вопросы по программированию - Как преобразовать рекурсивную функцию в нерекурсивную?

Как преобразовать рекурсивную функцию в нерекурсивную?

#python

#python

Вопрос:

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

В частности, я смотрю на последние 2 строки кода. Я надеюсь, что смогу получить помощь или подсказку, поскольку в настоящее время я совершенно невежественен.

 def newNode(data):
    return node(data)
  
# Function to print Leaf Nodes at
# a given level
def PrintLeafNodes(root, level):
    if (root == None):
        return
  
    if (level == 1):
        if (root.left == None and
            root.right == None):
            print(root.data, end = " ")
     
    elif (level > 1):
        PrintLeafNodes(root.left, level - 1) #convert from recursive to non recursive
        PrintLeafNodes(root.right, level - 1) #convert from recursive to non recursive

Комментарии:

1. Вместо повторного вызова самого метода (= рекурсивный) вы сохраняете значения в некоторых переменных и выполняете цикл while и больше не вызываете метод.

2. Вы должны показать свою попытку преобразования этого кода и спросить, пошло ли что-то конкретное в процессе не так, а не запрашивать решение. Это не служба кода

Ответ №1:

Вы можете изменить и адаптировать свой код, посетив этот веб-сайт. Также я попытался адаптировать код для вас.

 def PrintLeafNodes(root): 
      
    # Set current to root of binary tree 
    current = root  
    stack = [] # initialize stack 
    done = 0 
      
    while True: 
          
        # Reach the left most Node of the current Node 
        if current is not None: 
              
            # Place pointer to a tree node on the stack  
            # before traversing the node's left subtree 
            stack.append(current) 
          
            current = current.left  
  
          
        # BackTrack from the empty subtree and visit the Node 
        # at the top of the stack; however, if the stack is  
        # empty you are done 
        elif(stack): 
            current = stack.pop() 
            print(current.data, end=" ") # Python 3 printing 
          
            # We have visited the node and its left  
            # subtree. Now, it's right subtree's turn 
            current = current.right  
  
        else: 
            break
       
    print(current.data, end = " ")