Так, а теперь в методических целях можно дать и описание моей отладки этих примеров...
Начнём с чуть более простого, с фибоначчиевых функций. Я написал тестовый код (функции, соответсвенно я переименовал в FIB1 и FIB2):
Код:
: r 10 0 DO CR I FIB1 . I FIB2 . LOOP ; r
Собственно, вывод сразу даёт понять где косяк:
Код:
0 1
1 1
1 2
2 3
3 5
5 8
8 13
13 21
21 34
34 55
Т.е. краевой случай fib(0)=1 в первой функции обрабатывается неправильно, и даёт не единицу, а ноль. Решение:
Код:
: FIB1 ( n -- fib*n ) DUP 1 > IF
DUP 1- RECURSE SWAP 2 - RECURSE + ELSE
DROP 1 THEN ;
Приступаем ко второму (точнее, первому примеру) -- Аккерману.
Но сперва слегка похимичим с оформлением кода:
Код:
: ACK ( x y -- ack*x*y )
OVER 0= IF
NIP 1+ ELSE \ f(0,y)=y+1 (1)
DUP 0= IF
DROP 1- 1 RECURSE ELSE \ f(x,0)=f(x-1,1) (2)
1- OVER SWAP RECURSE \ f(x,y)=f(x-1,f(x,y-1)) (3)
SWAP 1- SWAP RECURSE THEN THEN ;
Так-то лучше...
Проверяем краевые случаи (как оно и полагается всегда при отладке рекурсивных функций):
Код:
0 0 ACK . \ (1)
4 0 ACK . \ (2)
А вот если попробовать
Код:
5 0 ACK . \ (2)
То тогда и вылетает. В принципе уже тогда возникает понимание, но давайте перепроверим, добавив в конец ACK:
Код:
: ACK ( x y -- ack*x*y )
...
SWAP 1- SWAP RECURSE THEN THEN
CR DUP .
;
На 4 0 мы получим около ста строчек (т. е. около ста рекурсивных вызовов). В случае 5 0 я успеваю заметить что строчек больше чем несколько сотен перед вылетом SPF. Т. е. причина вроде бы в том что просто стека возвратов элементарно не хватает. Переполнение стека.
Я там наворотил достаточно хитрую функцию для расширения стека возратов, что оказалось без толку, так переполнялся другой стек, обычный, а не возратов.
А для расширения обычного стека ничего особенного делать не надо:
Код:
CREATE ss 10000 ALLOT
HERE DUP S0 ! SP!
3 7 ACK .