こんにちは！一生Haskell勉強中のものです。ふるはしです。

再帰って、難しいですよね！
では再帰のどこが難しい(難しく感じる)のでしょうか？少し考えてみたいと思います。
二分木のデータ構造を例にとってみましょう。

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

木構造は空の木もしくは、値と左右の木を持つノードから構成されます。

すでにこの時点で難しいですよね！木の定義の中に木があるってどういうこと？って感じ
です。

Node a (Tree a) (Tree a)の部分がそれですね。

Tree a の部分に (EmptyTree | Node a (Tree a) (Tree a)) を代入して展開してみます
※以下はイメージしやすいように、型の定義をそのまま当てはめた擬似的な式です

Node a (EmptyTree | Node a (Tree a) (Tree a)) (EmptyTree | Node a (Tree a) (Tree a))

更に展開します

Node a
  (EmptyTree | Node a
     (EmptyTree | Node a (Tree a) (Tree a))
     (EmptyTree | Node a (Tree a) (Tree a))
  )
  (EmptyTree | Node a
     (EmptyTree | Node a (Tree a) (Tree a))
     (EmptyTree | Node a (Tree a) (Tree a))
  )
Node a
  (EmptyTree | Node a
     (EmptyTree | Node a (Tree a) (Tree a))
     (EmptyTree | Node a (Tree a) (Tree a))
  )
  (EmptyTree | Node a
     (EmptyTree | Node a (Tree a) (Tree a))
     (EmptyTree | Node a (Tree a) (Tree a))
  )

というように、どこまでも展開できてしまいます。
2回展開しただけで、すごいことになってしまいました。
木構造、なんて複雑なんだぁぁぁ！！！！と思われるかもしれません。

しかし元の定義は以下の通りで、比較的シンプルです。

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

無理に脳内で展開するから難しく感じるってことだったりするのでしょうか？
では脳内に展開しないで、どうやって再帰を理解すればよいのでしょうか？
ポイントは2つあると思います。

1つ目のポイント : モデル化

二分木とはこういうものだという、イメージを頭の中に持っておきます。

このイメージがあれば、木が木を持つということも比較的すんなり理解できるのではないかと思ったりしています。

優秀なプログラマはモデル化が上手くて、モデルを脳内にたくさん保管している人が多いように思います。

モデルは頭で描くだけでなく、悩みながら紙に書いたり、コードに落としたりしてやっと生み出されるものだったりします。

いざというときのために、モデル貯金しておきたいですね！

2つ目のポイント : 再帰を「宣言」として読む（数学的帰納法）

「木構造は空の木もしくは、値と左右の木を持つノードから構成されます。」という定義を、静的な「構造のルール」として信頼するということです。
つまり、HOWのプロセス(実際にどうやって作るか)を意識しないということになります。
なかなか難しいですよね！私は頭の中でトレースしたくなってしまいます。

では、なぜ頭の中でトレースしたくなるのでしょうか？

再帰を理解するためなのか、再帰が正しいのかを確かめるためなのか、はたまた別の何かでしょうか？

理解を深めるためなら、それは1つ目のポイントで触れたモデル化に繋がります。
正しいのかを確かめるためなら、それは定義の信頼で解決します。

ただ、他人が書いた再帰を信じられるか問題はあるかもしれないです(笑)

まとめ

再帰のモデルが脳内に存在しない場合は再帰をトレースして理解を深め、モデル化していく。 デバッグのために調査したい場合も再帰をトレースする。
省メモリでサクッといきたい場合は再帰をトレースせず定義を信じる。

余談

木構造を作成する関数を置いておくのでご自身でどう読んでいるかを客観的に観察してみると面白いかもです (https://paiza.io/ja/projects/new とかでHaskellを選択してペーストで動くはず)

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
    | x == a = Node a left right
    | x < a  = Node a (treeInsert x left) right
    | x > a  = Node a left (treeInsert x right)
    
main :: IO ()
main = do
    let nums = [8, 4, 1, 7, 3, 5]
    
    -- 木構造を作成
    let numsTree = foldr treeInsert EmptyTree nums
    
    -- 結果を表示
    print numsTree