Диаграмма последовательности / стека для рекурсивной функции - PullRequest
Новая
       7

Диаграмма последовательности / стека для рекурсивной функции

1 голос
/ 21 декабря 2010

для кода ниже: 

def printList(L):

   if L:

       print L[0]

       printList(L[1:])

У меня может быть такая диаграмма последовательности: 

# NON PYTHON PSEUDO CODE

PrintList([1,2,3])

  prints [1,2,3][0] => 1

  runs printList([1,2,3][1:]) => printList([2,3])

  => we're now in printList([2,3])

        prints [2,3][0] => 2

        runs printList([2,3][1:]) => printList([3])

    => we are now in printList([3])

          prints [3][0] => 3

          runs printList([3][1:]) => printList([])

          => we are now in printList([])

                "if L" is false for an empty list, so we return None

    => we are back in printList([3])

          it reaches the end of the function and returns None

  => we are back in printList([2,3])

    it reaches the end of the function and returns None

=> we are back in printList([1,2,3])

  it reaches the end of the function and returns None

Так что мой вопрос, если я изменю код на: 

def printList(L):

   if L:
       print L[0]
       printList(L[1:])
       print L[0]

Как изменится диаграмма последовательности, я хочу понять, что именно происходит во время выполнения этого кода.

1 Ответ

1 голос
/ 21 декабря 2010

Оператор print, вызываемый после рекурсивных вызовов, получит удар "на обратном пути".То есть каждое из ваших утверждений: «оно достигает конца функции и возвращает None» может быть изменено на «оно печатает текущее значение L [0], достигает конца функции и возвращает None», что будетбыть 3, 2 и 1 соответственно.

Примерно так: 

PrintList([1,2,3])
prints [1,2,3][0] => 1
runs printList([1,2,3][1:]) => printList([2,3])
=> we're now in printList([2,3])
    prints [2,3][0] => 2
    runs printList([2,3][1:]) => printList([3])
    => we are now in printList([3])
        prints [3][0] => 3
        runs printList([3][1:]) => printList([])
        => we are now in printList([])
            "if L" is false for an empty list, so we return None
        => we are back in printList([3])
        prints [3][0] => 3
        it reaches the end of the function and returns None
    => we are back in printList([2,3])
   prints [2,3][0] => 2
   it reaches the end of the function and returns None
=> we are back in printList([1,2,3])
prints [1,2,3][0] => 1
it reaches the end of the function and returns None
...