これはWORDIAN Advent Calendar 2022の1日目の記事です。

2日目はまだ決まっていません。

はじめに

再帰関数と聞くと、その実装に対して「難しい」と思う方が居られるかもしれません。

しかし、再帰関数は慣れてしまえばループ処理よりも簡潔に扱うことができたり、関数の挙動の定義を自然にコードにすることができたりと、とても便利なものです。

今回は、その再帰関数を定義するための考え方を言語化してみました。

サンプルコードはOCamlとRustで実装しています。 Rustのコードはplaygroundへのリンクも置いておくので、好きに弄って挙動を確かめてみてください。

考え方

まずは実装する関数の挙動について、以下の項目のことを考えます。

例えば「整数のリストの中身を全て足し合わせる関数」では、それぞれ

に相当し、階乗の計算では

に相当します。

そしてこれらの項目を使った汎用性のあるコードを書くと、

let rec f <引数> =
  if <関数の終了条件> then
    <単位元>
  else
    <演算> <計算後の値> (f <ワンステップ実行後の引数となる値>)

になります。

では、リストの中身を足すsum関数と階乗の計算をするfactorial関数をそれぞれ書いてみます。

let rec sum lst =
  match lst with
  | [] -> 0
  | x::xs -> 1 + (sum xs)

fn sum(lst : &mut Vec<usize>) -> usize {
  let i_opt = lst.pop();
  match i_opt {
    Some(i) => i + sum(lst),
    None => 0
  }
}

let rec factorial n =
  if n == 0 then
    1
  else
    n * (factorial (n - 1))

fn factorial(n : isize) -> isize {
  if n == 0 {
    1
  } else {
    n * (factorial(n - 1))
  }
}

いかがだったでしょうか。

関数の挙動を正確に定義すれば、パターンに従って再帰関数は綺麗に書くことができます。

これは返り値がリストになっても木構造になっても同じように終了条件・演算・その単位元を考えれば定義することができます。

もちろん、ループ処理の方が綺麗に書けることもありますが、再帰関数をたまには思い出してあげてください。