>>  <<  Usr  Pri  JfC  LJ  Phr  Dic  Rel  Voc  !:  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 ```

>>  <<  Usr  Pri  JfC  LJ  Phr  Dic  Rel  Voc  !:  Help  Dictionary