Блог

Я не думаю, что понимаю, как работает рекурсия в prolog

Следующий код (степенная функция)

 pow(_,0,1).
pow(X,Y,Z) :-
  Y1 is Y - 1  ,
  pow(X,Y1,Z1) ,
  Z is Z1*X
  .
  

Создает следующую трассировку:

 [trace]  ?- pow(2,2,X).
   Call: (6) pow(2, 2, _G368) ? creep
   Call: (7) _G444 is 2  -1 ? creep
   Exit: (7) 1 is 2  -1 ? creep
   Call: (7) pow(2, 1, _G443) ? creep
   Call: (8) _G447 is 1  -1 ? creep
   Exit: (8) 0 is 1  -1 ? creep
   Call: (8) pow(2, 0, _G446) ? creep
   Exit: (8) pow(2, 0, 1) ? creep
   Call: (8) _G450 is 1*2 ? creep
   Exit: (8) 2 is 1*2 ? creep
   Exit: (7) pow(2, 1, 2) ? creep
   Call: (7) _G368 is 2*2 ? creep
   Exit: (7) 4 is 2*2 ? creep
   Exit: (6) pow(2, 2, 4) ? creep
  

Я не понимаю, как работает последнее состояние: «Z равно Z1 * X». Когда вызывается эта функция? Когда достигается базовый вариант?
Как вообще вызывается базовый вариант?

Спасибо

Суть в том, что pow это не функция. Это предикат. На самом деле Prolog не оценивает pow , он пытается выполнить свои условия.

И когда достигается первое предложение? Это повторяется каждый раз. Но если второй аргумент не равен 0, а третий не равен 1 (или они являются переменными, которые могут быть объединены с этими значениями), он завершается с ошибкой. И когда первое предложение завершается неудачей, выполняется попытка второго.

Вы можете думать о pow функции, которая разделена на два предложения, которые имеют дело с разными значениями параметров. Функция является рекурсивной, которая запускается рекурсивным вызовом во втором предложении. Но после этого вызова все еще есть что-то, что нужно сделать, Z is Z1*1 цель. Эти «зависшие» вычисления выполняются, когда рекурсия завершается, и снова управляют «пузырьками» вверх, так сказать, на обратном пути. (Для такого рода рекурсии есть название, которое я не могу вспомнить).

Посмотрите на эту прокомментированную трассировку:

 [trace]  ?- pow(2,2,X).
      % initial call
   Call: (6) pow(2, 2, _G368) ? creep
      % the second clause is picked for this call, 
      % the third argument is an uninstantiated variable, represented by _G368
   Call: (7) _G444 is 2  -1 ? creep
      % the first goal in this claus is "Y1 is Y -1", which is here
      % translated with its bindings
   Exit: (7) 1 is 2  -1 ? creep
      % the is/2 goal has been called, and has provided a binding for "Y1"
   Call: (7) pow(2, 1, _G443) ? creep
      % this is the first recursive call, with the new arguments 2, 1 and an
      % undefined Z1
   Call: (8) _G447 is 1  -1 ? creep
      % again the second clause is used, this is the first goal in it,
      % calling is/2
   Exit: (8) 0 is 1  -1 ? creep
      % is/2 delivers a binding for the current Y1, 0
   Call: (8) pow(2, 0, _G446) ? creep
      % the next (second) recursive call; see how at this point non of the
      % "Z is Z1*X" "statements" have been reached
   Exit: (8) pow(2, 0, 1) ? creep
      % the second recursive call matches the first clause; this is where
      % the base case is used! it can immediately "Exit" as with the match
      % to the clause all bindings have been established already; the third
      % argument is instantiated to 1
   Call: (8) _G450 is 1*2 ? creep
      % now the recursion has terminated, and control is passed back to that
      % more recent calling clause (this was the one where Y1 has been bound
      % to 0); now the "Z is Z1*X" can be tried for the first time, and Z
      % can be instantiated ("unified")
   Exit: (8) 2 is 1*2 ? creep
      % this is the result of this unification, Z is bound to 2;
      % with this, this level in the stack of recursive calls has been completed...
   Exit: (7) pow(2, 1, 2) ? creep
      % ... and this is the result ("Exit") of this call, showing all
      % instantiated parameters
   Call: (7) _G368 is 2*2 ? creep
      % but this just brings us back one more level in the call stack, to a
      % pending execution (this was the one where Y1 has been bound to 1),
      % now the pending execution can be performed
   Exit: (7) 4 is 2*2 ? creep
      % here you see the result of the execution of is/2, binding Z to 4
   Exit: (6) pow(2, 2, 4) ? creep
      % and this finishes the initial call of the predicate, delivering a
      % binding for the X in the query, 4; you can tell that the recursive
      % call stack as been processed completely by looking at the "stack
      % depth indicator", (6), which matches the initial (6) when the trace
      % started (they don't necessarily start with 0 or 1).
  

Каждая строка в трассировке со звездочкой (*) использует правило «Z равно Z1 * X».

Этот код работает, предоставляя следующее рекурсивное определение степенной функции:

1. X^ 0 = 1 для всех X.
2. X^Y = X^(Y-1) * X

Переменные Z, Z1 и Y1 являются артефактами того факта, что Prolog нуждается в способе ссылки на промежуточные результаты; вы вызываете Y-1 Y1 и вызываете X ^(Y-1) Z1 .

Это приводит к базовому варианту путем уменьшения показателя степени (Y) на единицу (что дает Y1) на каждом уровне рекурсии до тех пор, пока Y = 0 и применяется первый случай определения.