Функция вызывается несколько раз с разными параметрами в задаче рекурсии - PullRequest
Новая
       31

Функция вызывается несколько раз с разными параметрами в задаче рекурсии

0 голосов
/ 30 января 2019

Я довольно новичок в программировании, и я только что познакомился с концепцией рекурсии.Мне подарили знаменитую проблему Ханойских Башен.Вот как парень в курсе, за которым я следую, решил это так: 

def printmove(fr,to):
   print('move from'+ str(fr)+'to'+str(to))


def Towers(n,fr,to,spare):
   if n == 1:
      printmove(fr,to)
   else:
      Towers(n-1,fr,spare,to)
      Towers(1,fr,to,spare)
      Towers(n-1,spare,to,fr)
Towers(4,"P1","P2","P3")

Чего я не понимаю, так это (и, скорее всего, это довольно очевидно, но я просто не могу обернутьсяэто) как он знает, когда переходить на второй рекурсивный вызов Towers (1, fr, to, spare)?

Ответы [ 2 ]

0 голосов
/ 31 января 2019

как он узнает, когда передавать на второй рекурсивный вызов Towers (1, fr, to, spare)?

На самом деле порядок выполнения между этими рекурсивными функциями определяется с помощьюэтот блок управления; 

if n == 1:
      printmove(fr,to)

Как видите, при достижении переменной n значение 1 , , оператор else не являетсябудет достигнут снова, и поэтому выполнение этой функции будет завершено ( рекурсия оборвется ).Как только он закончится, выполнение программы продолжится на следующей строке кода, которая Towers(1,fr,to,spare).Для вашего конкретного примера вы передали целочисленное значение 4 в вызов функции Towers(4,"P1","P2","P3"), поэтому я попытаюсь проиллюстрировать порядок выполнения вашей программы, чтобы он был более понятным;

  1. n = 4 , выполняется оператор else, первая строка кода в операторе else равна Towers(4 -1,fr,spare,to), в рекурсивное дерево добавляется новая функция выполнения
  2. n= 3 , оператор else выполняется, первая строка кода в операторе else равна Towers(3 -1,fr,spare,to), в дерево рекурсии добавляется новое выполнение функции
  3. n = 2 , elseоператор выполнен, первая строка кода в операторе else - Towers(2 -1,fr,spare,to), в рекурсивное дерево добавлено выполнение новой функции
  4. n = 1 , если оператор выполнен, printmove(fr,to)сработало, рекурсия прервана.
  5. Все предыдущие рекурсивные исполнения функций в дереве умерли в обратном порядке ( последний добавленный в дерево рекурсии -> первый умер ).
  6. Теперь единственная рабочая функция - это наш файл.первый вызов, Towers(4,"P1","P2","P3") для n = 4
  7. Выполнение программы продолжается со следующей строки кода, которая является Towers(1,fr,to,spare)
  8. Продолжение потока в этой логикедо тех пор, пока не прекратится последний вызов рекурсивной функции.

Итак, если бы в этом коде не было логики if-else , рекурсия Towers(n-1,fr,spare,to) никогда бы не сломалась и не начала бесконечную рекурсию.

0 голосов
/ 31 января 2019

В рекурсии каждая функция имеет свое собственное состояние.Таким образом, когда запускается функция Towers(n-1,fr,spare,to), она рекурсивно вызывает себя, уменьшая значение параметра на 1 при каждом вызове.После того, как эта функция соответствует критерию n==1, ее рекурсия заканчивается, а затем рекурсия начинается для Towers(1,fr,to,spare), и это продолжается.

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

def printmove(fr,to):
   print('move from'+ str(fr)+'to'+str(to))


def Towers(n,fr,to,spare):
   print "n: " , n 
   if n == 1:
      printmove(fr,to)
   else:
      Towers(n-1,fr,spare,to)
      print "did A"      
      Towers(1,fr,to,spare)
      print "did B"
      Towers(n-1,spare,to,fr)
      print "did C"
Towers(4,"P1","P2","P3")

Я не публикую здесь ответ, но в основном первая функция запускается до тех пор, пока n не выйдет из4 к 1, затем второй и так далее.

...