Sicp - страница 6

1.2. Процедури и процесите, които генерират

Като цяло, итеративен процес е този, чието състояние може да бъде описано от краен брой променливи на състоянието, плюс предварително дефинирано правило, което определя как тези променливи на състоянието се променят от стъпка на стъпка, и плюс (евентуално) тест за прекратяване, който определя условията, при които процесът трябва да приключи. При изчисляване на n! броят на стъпките нараства линейно с n. Такъв процес се нарича линеен итеративен процес.

Можете да погледнете разликата между тези два процеса от друга гледна точка. В итеративния случай във всеки момент програмните променливи дават пълно описание на състоянието на процеса. Ако спрем процеса между стъпките, трябва само да дадем на интерпретатора стойностите на трите програмни променливи, за да продължи изчислението. Това не е случаят с рекурсивен процес. В този случай има допълнителна "скрита" информация, която се съхранява от интерпретатора и която не се съдържа в програмните променливи. Той указва "къде" се намира процесът по отношение на веригата от чакащи операции. Колкото по-дълга е веригата, толкова повече информация трябва да се съхранява 30 .

При противопоставянето на итерация и рекурсия трябва да се внимава да не се бърка концепцията за рекурсивен процес с концепцията за рекурсивна процедура. Когато казваме, че една процедура е рекурсивна, имаме предвид факт от синтаксиса: дефиницията на процедура се отнася (пряко или косвено) до самата процедура. Когато говорим за процес, следващ, да речем, линеен рекурсивен модел, говорим за еволюцията на процеса, а не за синтаксиса, в който е написана процедурата. Може да изглежда странно, например, да се каже, че "една рекурсивна процедура описва итеративен процес." Процесът обаченаистина е итеративен: състоянието му е напълно описано от три променливи на състоянието и за да осъществи този процес, интерпретаторът трябва да съхрани стойността само на три променливи.

Разграничението между процеси и процедури може да бъде объркващо, отчасти защото повечето реализации на конвенционалните езици (включително Ada, Pascal и C) са проектирани така, че интерпретирането на всяка рекурсивна процедура отнема отпечатък от паметта, който расте линейно с броя на извикванията на процедурата, дори ако процесът, който описва, по принцип е итеративен. Като следствие, тези езици са в състояние да опишат итеративни процеси само със специални „циклични конструкции“ като do, repeat, until, for и while. Реализацията на Scheme, която ще разгледаме в Глава 5, е свободна от този недостатък. Той ще извърши итеративен процес, използвайки фиксирано количество памет, дори ако е описан от рекурсивна процедура. Това свойство на езиковата реализация се нарича поддръжка на опашната рекурсия. Ако реализацията на езика поддържа рекурсия на опашката, тогава итерацията може да бъде изразена с помощта на обикновения механизъм за извикване на функция, така че специалните циклични конструкции да имат смисъл само като синтактична захар 31 .

30 Когато обсъждаме прилагането на процедури с регистрови машини в Глава 5, ще видим, че итеративният процес може да бъде реализиран "хардуерно" като машина, която има само краен набор от регистри и без допълнителна памет. Обратно, рекурсивен процес изисква машина със спомагателна структура от данни, наречена стек.

Речникът multitran.ru дава превода "крайна рекурсия". Нашата версия изглежда по-елегантна и запазва метафората, съдържаща се в английския термин. - прибл. превод

31 Дълго време се смяташе, че опашната рекурсия е специален трик за оптимизиране на компилаторите. Ясна семантична основа за рекурсия на опашката беше открита от Карл Хюит (Hewitt 1977), който я изрази чрез модел на изчисление за „предаване на съобщения“ (ние ще изследваме този модел в

Глава 1 Изграждане на абстракции с процедури

Всяка от следните две процедури дефинира начин за добавяне на две положителни цели числа с помощта на процедурите inc, която добавя 1 към своя аргумент, и dec, която изважда 1 от своя аргумент.

(дефинирайте (+ a b) (ако (= a 0)

Използвайки модела на заместване, илюстрирайте процеса, генериран от всяка от тези процедури чрез изчисление (+ 4 5) . Дали тези процеси са итеративни или рекурсивни?

Следната процедура изчислява математическа функция, наречена функция на Акерман.

(дефинирайте (A x y) (условие ((= y 0) 0)

((= x 0) (* 2 y)) ((= y 1) 2) (иначе (A (- x 1)

Какви са значенията на следните изрази?

Разгледайте следните процедури, където A е процедурата, дефинирана по-горе:

(дефиниране (f n) (A 0 n)) (дефиниране (g n) (A 1 n)) (дефиниране (h n) (A 2 n))

(дефинирайте (k n) (* 5 n n))

Дайте кратки математически дефиниции на функциите, изчислени чрез процедурите f, g и h за положителни цели числа на n. Например (k n) се оценява на 5n 2 .

глава 3). Вдъхновени от това, Джералд Джей Съсман и Гай Луис Стийл мл. (Вижте Стийл 1975) изгради рекурсивен интерпретатор на схема с опашка. Стийл по-късно показа, че рекурсията на опашката е следствие от естествения начин, по който се компилират извиквания на процедури (Стийл 1977). Стандартът IEEE Scheme изисква всички реализации на Scheme да поддържат рекурсия на опашката.

1.2. Процедури и процесите, които генерират

1.2.2. дървовидна рекурсия

Има друга обща схема за изчисление, наречена дървовидна рекурсия (дървовидна рекурсия). Като пример, разгледайте изчислението на поредица от числа на Фибоначи, в която всяко число е сумата от предходните две:

0, 1, 1, 2, 3, 5, 8, 13, 21, . . .

Общото правило за числата на Фибоначи може да се формулира, както следва: