【自分的レシピ】elixirでの再帰関数の動かし方

再帰関数っていいよね

たまにelixirでも「for使いてぇ~」って邪悪な思想に染まる時がありますが
再帰関数やEnumなどを使って目標を達成できると最高の気分になりますね
再帰関数に至っては関数型言語に共通することです

自分の簡潔な言葉で「再帰関数って何なん？」という問いに答えると

関数の中で自分自身(関数)を呼ぶ関数でっせ

となります。どういうことやねん
javascriptとpython使って5回、引数でもらったメッセージを出力する関数を再帰関数使って書いてみました
簡略化のため、今回は5回固定にしておきます

const greeding = (message, num) => {
  if(num===5){
    #条件に達した時に終了
    console.log("--> all finished!");
    return true;
  } else {
    console.log(message);
    #ここで自分自身(関数)を呼び出している
    greeding(message, num+1);
  }
}
greeding("hello world!", 0);

#result
# hello world!
# hello world!
# hello world!
# hello world!
# hello world!
# --> all finished!

pythonの場合

def greeding(message, num):
  if num == 5:
    #条件に達した時に終了
    print("--> all finished!")
    return True
  else:
    print(message)
    #ここで自分自身を呼び出す
    greeding(message, num+1)
    
greeding("hello world!", 0)

#result: 同じなのでカット

#for使おうぜ
for i in range(5):
  print("hello world!")
print("--> all finished!")

停止性について低姿勢で考察する

なんとなーく分かってもらえれば光栄です
僕もなんとなーくでやってるので
従来のfor文と異なるのは「ここで停止します」ということを明確に宣言してあげる必要があります
難しい本には「停止性についての議論」と記述されています

例えばpythonとかだったらif文使ってこの条件の時にreturn書いて
関数内の処理が終了するということを明確にしてあげればいいってことです
while書く時に終了条件書きますよね。あれと同じようなもんです

この停止性についてfor文だとどうなっているかというと、iteratorたるものがあって
列挙可能なデータを1つずつ取り出してきてくれます
それで、これ以上取り出せませんってなったときにNoneやらを返して処理を終了させるというものです

lst_data = [1,2,3,4,5]

#take: 1,  rest: [2,3,4,5]
#take: 2, rest: [3,4,5]
#take: 3, rest: [4,5]
#take: 4, rest: [5]
#take: 5, rest: []
#もう残ってませんのでNone返しますわ

もっと詳しく知りたい方は「言語名イテレーター」とかで調べてみてください
有志の猛者たちがアホほど分かりやすく解説してます

elixirにはforはないから再帰関数を使うしかない

これまでの流れを踏まえて考えれば、for文のないelixirでもループ処理は書けそうな気がしてきた(適当
関数内で自分自身(関数)を呼び出して、終了条件を書いてあげればいいんでしょ？

その通り。察しがいいですね
その前にelixirというか関数型言語での便利な構文について少し触れておきます
ゆるく理解するElixirのデータ構造体と簡単なパターンマッチング例でも若干触れてますが
配列の先頭要素を取り出す際に

lst_data = [1,2,3]
[head | tail] = lst_data

IO.puts(head) #result: 1
IO.puts(inspect tail) #result: [2,3]

こんな書き方をしています
構文に関しての名前は特になくて著書によれば「ヘッドとテイル」とあるので、そう呼びます
ヘッドとテイルと言ってるんですけど変数名は実は何でもOK

[a  | b] = lst_data

配列の要素が残り1つになった場合には

[head | tail] = [1]

#head: 1
#tail: []

tailにはが与えられています
この空の配列に対してヘッドとテイルを使うとerrorになります

[head | tail] = []
#(MatchError) no match of right hand side value: []

一度まとめておくと

配列に対してヘッドとテイルを使用することで先頭要素と残りの要素(配列)に分割することが可能
配列の残り要素が1つの場合にはheadに要素が、tailには空の配列が与えられる
空の配列に対してヘッドとテイルを使用するとerrorになる

で、何かって？このヘッドとテイルが何かiteratorに似てるなーって思いませんか?
Noneやらが空の配列になっただけじゃんって考えるとそっくりじゃないですか!!

準備は整った

ここまで話を膨らませるともう何となく書けちゃいそうですね
データを列挙して、終了する条件を記述してあげればOKってことなので
ヘッドとテイルの場合には空の配列になった時に終了させてやればよさそうですね
配列に受け取った文字列を全て出力するという処理を書いてみましょう
elixir

defmodule Output do
  def show_msg([]), do: :ok
  def show_msg([head | tail]) do
    IO.puts(head)
    show_msg(tail)
  end
end

msg_lst = [
  "hello okb",
  "goodbye okb",
  "I love you"
]

Output.show_msg(msg_lst)
#result
# hello okb
# goodbye okb
# I love you

詳しいことは別の記事に書こうと思いますが
elixirでは関数の引数に対してマッチングをすることが出来ます

def show_msg([]), do: :ok

という関数では第1引数が空の配列の場合に実行されます
それ以外の場合(配列に要素が存在している)には

def show_msg([head | tail]) do ... end

こちらの関数がヒットします
elixirでは同名の関数何個あってもOKで、引数を使って条件分岐が可能です
その上、引数内でヘッドとテイルやパターンマッチが使えてしまうという...超強力です

つまりはヘッドとテイルを使って配列の要素を取り出しつつ
restが空の配列になった時点で終了になるという動き方をします

#take: 1,  rest: [2,3,4,5] -> show_msg([head | tail]) --> continue
#take: 2, rest: [3,4,5] -> show_msg([head | tail]) --> continue
#take: 3, rest: [4,5] -> show_msg([head | tail]) --> continue
#take: 4, rest: [5] -> show_msg([head | tail]) --> continue
#take: 5, rest: [] -> show_msg([]) --> finished!!

配列じゃない場合どうするの？

再帰関数を使うにあたって「停止性」を保証してあげればいいので
基本的に考え方は同じです
ifやらでマッチさせる対象が配列から数値や文字列に変わるだけです

指定回数「hello!」を出力する

defmodule Output do
  #numが0の時にヒットする
  def show_hello(num) when num === 0, do: :ok
  def show_hello(num) do
    IO.puts("hello !")
    #次の再帰に渡す引数を-1(いずれ0になる)
    show_hello(num-1)
  end
end

Output.show_hello(10)

#result
# hello !
# hello !
#:
#:
# hello ! 10回出力されて終了

文字列を先頭から1文字ずつ取得して表示していく
かなり強引ですが文字列でも余裕でいけます

defmodule Output do
  def first_str(str) when str === "", do: :ok
  def first_str(str) do
    first = String.slice(str, 0..0)
    rest = String.slice(str, 1..String.length(str)-1)
    IO.puts("--> first: #{first}")
    first_str(rest)
  end
end


Output.first_str("abcdefg")
--> first: a
# --> first: b
# --> first: c
# --> first: d
# --> first: e
# --> first: f
# --> first: g

まとめ

再帰関数を記述際に考えるべき重要な点は
この処理は停止するかどうか ということです
停止性を実現するためにはifなどを用いて条件によって終了させてあげれば良いです
加えて再帰関数では条件を作成した後にその条件を満たす場合が発生するように
引数の値が変化するようにしてあげる必要があります

配列: 要素が1つ取得される(ヘッドとテイル)
数値: +1される -1される　など
文字列: 先頭の1文字が取得される 1文字増える etc...

全ての引数の値が全て同じであると再帰が無限になってしまうので気をつけましょう

まとめのまとめ

停止性を保証する(条件を作成する)
次の再帰に全ての引数で同じ値を渡さない

この記事の続編として再帰関数には不可欠なアキュムレーターについてまた触れます
長くなってすんません。やっぱり再帰関数っていいよね

やわらかテック

興味のあること。業務を通して得られた発見。個人的に試してみたことをアウトプットしています🍵