2012-12-18 20 views
8

たとえば、次の関数はアキュムレータを持たないため、まだテール再帰的ですか?テール再帰に必ずアキュムレータが必要ですか?

belong:: (Ord a) => a -> [a] -> Bool 
belong a [] = False 
belong a (h:t) 
    | a == h = True 
    | otherwise = belong a t 

機能のすべての計算は、再帰呼び出しの前に処理され、尾を再帰的とみなされるのに十分な条件でありますか?

+1

はい、それは十分な – m09

+0

末尾再帰では、厳格な言語で最高のですが、Haskellで、物事は少し異なっています。 [この質問](http://stackoverflow.com/questions/13042353/does-haskell-have-tail-recursive-optimization)では、この問題に関する優れた情報が得られます。 – AndrewC

答えて

10

末尾再帰は必ずしもアキュムレータを必要としません。アキュムレータは、再帰呼び出しの各レベルで使用する余分なスペースを必要とせずに、再帰呼び出しチェーンを介して部分的な結果を通信する手段として末尾再帰で使用されます。例えば、カノニカルテール再帰的階乗関数は、今まで構築された部分積を伝搬させるためにアキュムレータを必要とする。ただし、再帰呼び出しからそのサブコールに情報を伝達する必要がない場合、アキュムレータは必要ありません。

あなたが提供してきた機能は確かに末尾再帰であるが、それは、アキュムレータを必要とするか、または使用していません。リスト内の要素を検索するとき、再帰はそれまでに見た要素のすべてが検索対象の特定の要素と等しくないことを覚えておく必要はありません。探している要素と検索する項目を知る必要があります。

希望すると便利です。

+0

多くのお役に立った!いい説明。 – user1493813

0

Tail recursionは必ずしもアキュムレータを必要としません。しかし、アキュムレータがしばしば使用される。ヒント、「アキュムレータ」についてのウィキペディアの記事を検索してください。

関連する問題