>>  <<  Ркв  Ввд  JfC  LJ  Фрз  Слв  Изм  Рзг  !:  Помощь  Словарь

22. Рекурсия

Факториал ! целого числа n определяется как произведение n и факториала n-1 , с граничным условием: факториал 0 равен 1 . Такое определение называется рекурсивным, поскольку функция определяется через вызов самой себя (function recurs).

Рекурсивное определение можно дать при помощи союза сообразно, выбирающего вариант обращения к себе до тех пор, пока не выполнено граничное условие. Например:
   factorial=: 1:`(]*factorial@<:) @. *
   factorial "0 i.6
1 1 2 6 24 120
Заметьте, что 1: обозначает постоянную функцию, результат которой всегда 1 .

В предложении (sum=: +/) i.5 глаголу, определенному фразой +/ , перед использованием присваивается имя, но в предложении +/ i.5 он используется анонимно. В определении factorial присваивание имени было необходимо для того, чтобы сослаться на него внутри определения. Однако, слово $: позволяет сослаться на себя без присвоения имени, открывая возможность написания анонимных рекурсивных определений. Например:
   1:`(]*$:@<:) @. * "0 i. 6
1 1 2 6 24 120
В задаче о Ханойской Башне, набор n дисков (каждый своего размера) должен быть перемещен со стержня A на стержень B, используя третий стержень C, при ограничении, что больший диск нельзя класть на меньший. Следующее, представляет из себя рекурсивное определение этого процесса:
   h=: b`(p,.q,.r)@.c
    c=: 1: < [
    b=: 2&,@[ $ ]
      p=: <:@[ h 1: A. ]
      q=: 1: h ]
      r=: <:@[ h 5: A. ]

   3 h x=: 'ABC'
AABACCA
BCCBABB

   0 1 2 3 4 <@h"0 1 x
++-+---+-------+---------------+
||A|AAC|AABACCA|AACABBAACCBCAAC|
||B|CBB|BCCBABB|CBBCACCBBAABCBB|
++-+---+-------+---------------+

Упражнения

22.1   Используйте следующее для упражнений по чтению и письму: 
   f=:1:`(+//.@(,:~)@($:@<:))@.*         Биномиальные коэффициенты
   <@f"0 i.6                             Упакованные бином. коэффициенты
   g=:1:`((],+/@(_2&{.))@$:@<:)@.*       Числа Фибоначчи


>>  <<  Ркв  Ввд  JfC  LJ  Фрз  Слв  Изм  Рзг  !:  Помощь  Словарь