Как работают эти функции Треугольника Паскаля?

Я читаю Концепции, методы и модели компьютерного программирования, и в начале есть код, который я просто не могу понять, как бы я ни старался.

declare Pascal AddList ShiftLeft ShiftRight

fun {Pascal N}
   if N==1 then [1]
   else
      L in
      L = {Pascal N-1} % Recursion
      {AddList {ShiftLeft  L}
               {ShiftRight L}}
   end
end

fun {ShiftLeft L}
   case L of H|T then
      H|{ShiftLeft T}  % Recursion
   else [0]
   end
end

fun {ShiftRight L}
   0 | L
end

fun {AddList L1 L2}
   case L1 of H1|T1 then
      case L2 of H2|T2
      then
     H1+H2|{AddList T1 T2} % Recursion
      end
   else nil
   end
end

Я как бы понимаю языковые конструкции (это введение в них), но вещь, которая действительно стоит на моем пути, — это рекурсия.

Я пытаюсь поставить метку на каждый вызов рекурсии, который будет абстрактно говорить, что здесь происходит, но я просто не могу понять это.

Я прошу четких и простых объяснений того, как работают эти функции.


recursion oz mozart
person MasterMastic    schedule 06.03.2013    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Начните с N == 1: это просто. Результат просто [1].

Теперь проверьте N == 2:

First we calculate L = {Pascal N-1} = {Pascal 2-1} = {Pascal 1} = [1]
Now shifted to the left: [1 0]
Shifted to the right: [0 1]
AddList just adds elementwise. So the result for {Pascal 2} is [1 1].

Теперь для N == 3:

{Pascal 2} = [1 1]
Shifted left:  [1 1 0]
Shifted right: [0 1 1]
Added:         [1 2 1]

Конечно, программа работает наоборот: она начинается с большего N. Но в начале функции Pascal программа многократно повторяется, пока параметр N не станет 1. Что-то вроде этого:

{Pascal 3}
   {Pascal 2}
      {Pascal 1}
      [1]
   [1 1]
[1 2 1]

Редактировать: на самом деле в программе есть виды рекурсии. Первый в Pascal начинается с некоторого целого числа N и рекурсивно спускается до 1.

Другой (во вспомогательных методах) начинается со списка, состоящего из головы и хвоста, и останавливается, как только список становится пустым, т.е. больше не может быть разделен. (При этом используются так называемые списки минусов, рекурсивный по своей сути тип данных.)

person wmeyer    schedule 06.03.2013

arrow_upward
0
arrow_downward

объяснение wmeyer очень приятно. Я просто хочу добавить, возможно, полезную «визуализацию» -->

Прежде всего, я использую оригинальную версию книги (PDF), и функции выглядят так -->

declare Pascal AddList ShiftLeft ShiftRight
fun {Pascal N}
   if N==1 then [1]
   else
      {AddList {ShiftLeft {Pascal N-1}} {ShiftRight {Pascal N-1}}}
   end
end

fun {ShiftLeft L}
   case L of H|T then
      H|{ShiftLeft T}
   else [0] end
end

fun {ShiftRight L} 0|L end

fun {AddList L1 L2}
   case L1 of H1|T1 then
      case L2 of H2|T2 then
         H1+H2|{AddList T1 T2}
      end
   else nil end
end

Представьте, что вы хотите увидеть восьмую строку треугольника Паскаля. Вы собираетесь войти:

{Browse {Pascal 8}}

то есть вы хотите отобразить результат подачи 8 функции Pascal, как определено в книге/здесь.

Сначала функция проверяет, равно ли только что переданное значение 1 (что не будет истинным до ПОСЛЕДНЕЙ итерации рекурсии (или последнего рекурсивного вызова(ов)), когда [1] (из if N= =1) будет возвращен как результат ЭТОГО ВЫЗОВА Pascal и передан обратно вверх по «цепочке» выполнения (Pascal) к следующему самому последнему вызову (где этот результат, [1], добавляется к результату соответствующий ShiftLeft или ShiftRight, а затем ЭТОТ результат отправляется обратно вверх по цепочке, и так далее, пока не достигнет первого (Pascal 8).Таким образом, вызовы идут на 8 уровней в глубину, а затем передают ответы обратно на эти уровни до тех пор, пока вы получите окончательный ответ... но я забежал вперед.

Хорошо, поскольку вы скормили 8, тест N == 1 терпит неудачу, и поэтому вместо того, чтобы иметь возможность сдвигать «списки» и сразу же добавлять их вместе в предложении else, функция не может сделать это с неопределенными терминами в «уравнениях» говорит: «Я попробую N - 1! Может быть, ЭТО будет окончательным ответом!!» (для ShiftLeft И ShiftRight - так что это ветвление происходит каждый раз, когда происходит рекурсино)

Итак, функция ждет ответа от Паскаля N-1 внутри ShiftLeft и ShiftRight... ждет, ждет...

Что ж, {Pascal 7} также не будет верным для N==1, поэтому более новые вызовы ("вызовы", 2-й И 3-й вызовы, левый и правый!) Паскаля ОБА также будут спрашивать: "Что такое Паскаль N - 1". (7-1 на этот раз) и оба будут ждать ответа...

Это продолжается и продолжается, и продолжается, и продолжается.... о, подождите, пока N==1!

Затем [1], список, возвращается BACK UP THE CHAIN... таким образом, каждый последующий вызов функции ожидания, самый последний сначала (имейте в виду, что все это происходит все больше и больше по пути вниз, чтобы добраться сюда до «дна» где N==1 по мере увеличения расщеплений (вызывая ShiftLeft и ShiftRight одновременно при каждом вызове)) может, наконец, выполнить расчет AddList с ответами, которые он ждал от своих личных, частных вызовов ShiftLeft и ShiftRight.

Все спускается вниз, разбиваясь на все больше и больше вызовов функций, затем мы возвращаемся наверх и, наконец, можем получить ответ. Этот окончательный ответ — это предложение else первого вызова функции Паскаля, {Pascal 8}, которое теперь внутри (поскольку восьмая строка треугольника Паскаля — [1 7 21 35 35 21 7 1]) будет выглядеть так:

{AddList [1 7 21 35 35 21 7 0] [0 7 21 35 35 21 7 1]} ‹ -- по крайней мере, я думаю, что так выглядят окончательные списки, которые нужно добавить

После добавления один список возвращается как окончательный ответ и отображается: [1 7 21 35 35 21 7 1]

person crh777    schedule 30.06.2019