22. 遞迴

階乘函數 ! 通常定義的方式為， n階乘等於 n 乘以 n-1 階乘，且 0 的階乘為 1。如此定義的方式稱之為遞迴，因為欲定義的函數出現在其定義中。

案例敘述可以用來做遞迴定義。A case statement 可以用來make a recursive定義, case that employs 函數 under 定義being chosen repeatedly until terminating case is encountered. 例如:

   factorial=: 1:`(]*factorial@<:) @. *
   factorial "0 i.6
1 1 2 6 24 120

其中 1: 代表函數值為 1 的常數函數。

在句子 (sum=: +/) i.5 中，由 +/ 定義的動詞，使用前先命名為 sum，但在句子 +/ i.5 中直接匿名執行。前例階乘函數的定義中，分子呼叫自身，命名很重要。但是單字 $: 提供自我呼叫的功能，允許匿名遞迴定義。例如:

   1:`(]*$:@<:) @. * "0 i. 6
1 1 2 6 24 120

在河內塔之謎，n個大小不同的盤子要從 post A搬到post B，用post 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	Use following as exercises in reading與writing: f=:1:`(+//.@(,:~)@($:@<:))@.* Binomial Coeffs <@f"0 i.6 Boxed binomials g=:1:`((],+/@(_2&{.))@$:@<:)@.* Fibonacci

下個 • 前個 • 字彙 • 索引 • 主選單