Рекурсия
Рекурсия
Рекурсия - это основной механизм программирования итерационных конструкций языка Смолток. Рассмотрим реализацию метода Fibo класса Integer.
-- Фибоначчи
-- выдать N число Фибоноччи, где N - объект-адресат
-- Числа Фибоначчи задаются следующей последовательностью:
-- x1=1, x2=1, xi=xi-1+xi-2
Fibo
self<3 ifTrue: [ ^1 ]
ifFalse: [ ^ (self - 1) Fibo + (self - 2) Fibo ]
Теперь можно выполнить следующее выражение:
#(1 2 3 4 5 6 7 10 20) собрать: [ :m| m Fibo ]
В качестве следующего примера рассмотрим программу для решения известной головоломки "Ханойские башни".
Постановка задачи. Имеется 3 штырька, на штырьке #1 расположены кольца разного диаметра в порядке убывания их размера снизу вверх. Требуется переложить кольца со штырька #1 на штырек #2, пользуясь штырьком #3 как промежуточным, таким образом, чтобы кольца на штырьке #2 располагались в порядке убывания их диаметра и чтобы в процессе перекладывания кольцо большего диаметра никогда не накладывалось на кольцо меньшего диаметра.
1 Этап. Спецификация метода
a) объект-адресат - это целое число (количество колец). Следовательно, данный метод будет принадлежать классу целых чисел.
b) объекты-параметры - символы '1', '2', '3' (информация: с какого штырька на какой нужно переложить кольцо и какой использовать как дополнительный)
c) результат - вывод на экран информации о последовательности выполнения данной задачи.
Следовательно, вызов метода будет осуществляться следующим образом:
10 ханойC: '1' на: '2' через: '3'
2 Этап. Реализация метода ханойС: x на: y через: z.
Данная задача решается рекурсивно.
a) Базис. Если число колес равно 1, то нужно просто переложить это кольцо c х на y.
b) Если число колес равно К, то нужно переложить со штырька х на штырек z K-1 колец, а затем переложить самое большое K-е кольцо на y и переложить все остальные K-1 колец на y.
ханойС: x на: y через: z
"головоломка 'Ханойские башни'"
self := 1
ifTrue: [ СистемнаяИнформация поместитьВсеПоследующие:
'Переложить со штырька ',x,' на штырек ',y;
символВК. ]
ifFalse: [ (self - 1) ханойС: x на: z через: y.
СистемнаяИнформация поместитьВсеПоследующие:
'Переложить со штырька ',x,' на штырек ',y;
символВК.
(self - 1) ханойС: z на: y через: x ]
Теперь можно добавить полученный метод в класс Integer (Целое) и выполнить программу для числа колец, равного, например, 10:
10 ханойС: '1' на: '2' через: '3'
Реализация этого метода в системе Smalltalk Express выглядит следующим образом:
hanoiFrom: x to: y by: z result: aStream
"головоломка 'Ханойские башни'"
self == 1
ifTrue: [ 'Переложить со штырька ' printOn: aStream.
x printOn: aStream.
'на штырек ' printOn: aStream.
y printOn: aStream.
(10 asCharacter) printOn: aStream.]
ifFalse: [ (self - 1) hanoiFrom: x to: z by: y result: aStream.
'Переложить со штырька ' printOn: aStream.
x printOn: aStream.
'на штырек ' printOn: aStream.
y printOn: aStream.
(10 asCharacter) printOn: aStream.
(self - 1) hanoiFrom: z to: y by: x result: aStream.]
Пример работы (пункт Show – "Показать"):
|aStream|
aStream := WriteStream on: String new.
10 hanoiFrom: 1 to: 2 by: 3 result: aStream.
aStream contents.
И, для полноты картины, приведем пример этой программы на языке Паскаль:
Program Han;
const Step : integer = 0; {Глобальный счетчик итераций - шагов}
procedure Hanoi(N : integer; X, Y, Z : char);
{ X-откуда, Y-куда, Z-через}
begin
if N=1 then
begin
Step:= Step +1;
writeln(Step:3,' Переложить со штырька ',X,' на штырек ',Y);
end
else
begin
Hanoi(N-1, X,Z,Y);
Step:= Step +1;
writeln(Step:3,' Переложить со штырька ',X,' на штырек ',Y);
Hanoi(N-1, Z,Y,X);
end;
end;
var N : integer;
begin
writeln;
writeln('ХАНОЙСКИЕ БАШНИ');
writeln;
write('Введите число колец: ');
readln(N);
Hanoi(N,'A','B','C');
end.
