>>  <<  Ndx  Usr  Pri  Phr  Dic  Rel  Voc  !:  wd  Help  Dictionary

22. Recursion

The factorial function ! is commonly defined by the statement that factorial n is n times factorial n-1 , and by the further statement that factorial 0 is 1 . Such a definition is called recursive, because the function being defined recurs in its definition.

A case statement can be used to make a recursive definition, the case that employs the function under definition being chosen repeatedly until the terminating case is encountered. For example:
   factorial=: 1:`(]*factorial@<:) @. *
   factorial "0 i.6
1 1 2 6 24 120
Note that 1: denotes the constant function whose result is 1 .

In the sentence (sum=: +/) i.5 the verb defined by the phrase +/ is assigned a name before being used, but in the sentence +/ i.5 it is used anonymously. In the definition of factorial above, it was essential to assign a name to make it possible to refer to it within the definition. However, the word $: provides self-reference that permits anonymous recursive definition. For example:
   1:`(]*$:@<:) @. * "0 i. 6
1 1 2 6 24 120
In the Tower of Hanoi puzzle, a set of n discs (each of a different size) is to be moved from post A to post B using a third post C and under the restriction that a larger disc is never to be placed on a smaller. The following is a recursive definition of the process:
   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|
++-+---+-------+---------------+

Exercises

22.1   Use the following as exercises in reading and writing: 
   f=:1:`(+//.@(,:~)@($:@<:))@.*         Binomial Coeffs
   <@f"0 i.6                             Boxed binomials
   g=:1:`((],+/@(_2&{.))@$:@<:)@.*       Fibonacci


>>  <<  Ndx  Usr  Pri  Phr  Dic  Rel  Voc  !:  wd  Help  Dictionary