再帰

この間hayamizuさんとあった時に自分がHaskellでつまずいていた再帰について話をしました
正直どうして

   map f (x:xs) = f x : map f f xs

なのか分からなかったのです
どうしてリストを最初の値とそれ以外の値に分けるのかふつうのHaskellの図解を見ても分からなかったのです
(ちなみにふつうのHaskellプログラミングではリストの扱いが入り子形式で記載されています)

その時に話した事が

    map square [1,2,3] →[1,4,9]

これは簡単に分かると思いますが
map関数はリストを受け取ってリストを返す関数です
square関数は値を二乗する関数です
map squareはsquareを引数として受け取ってかえす高階関数という事です
値[1,2,3]を入れて値を二乗してその値をそのまま返すと[1,4,9]となります
ここからは以上をふまえた上での再帰の話

     square 1 : map square [2.3]
　　　　　　　      ↓　ここの部分を分かりやすくすると
　　　　　　    square 2　： square 3
　　　　　　　    この部分が再帰です

再帰処理とは(x:xs)の構造からも分かるようにまず最初の数値を呼び出した後また最初の数値を呼び出し
呼び出した順に処理を走らせる事です
そのために、まず(最初の数値)(それ以外の数値)に分ける必要があるのです
ただこれだけでは分かりづらいと思うので併せて階乗についても書こうと思います

　  5!  = 5 × 4 × 3 × 2 × 1

これが階乗です
これをまず頭に入れて再帰について考えたいと思います

    fact :: Int < Int
    fact 0 = 1
    fact n = n * fact (n-1)
この式に5の階乗を実際に値として代入したいと思います
fact :: Int < Int　で型は整数値→整数値で表現されます
次にfact 0 = 1という定義があります
　　　fact n = n * fact (n-1)のnに5を代入します
　　　fact 5 = 5 * fact (5-1)
　　　fact 4 = 4 * fact (4-1)
　　　fact 3 = 3 * fact (3-1)
　　　fact 2 = 2 * fact (2-1)
　　　fact 1 = 1 * fact (0-1)
　　　fact 0 = 1 * fact (1-1)

ちょっとループっぽいけど、再帰について分かってもらえたのではないでしょうか？
数値を繰り返し呼び出して使う事が再帰なんですね
また、リストは

こう考えると分かりやすいです
※青の部分は連結部
こういう図を作るのが大変でした(^^;)
Special thanks by hayamizuさん