CS放浪記　〜再帰ってどんな動きをしているの？〜

はじめに

こんにちは。ひろです。CS放浪記へようこそ！
今回から数回にわたり「再帰」を見ていきます。再帰についての簡単な紹介と、実行時にどのような動きをしているかを解説いたします。

再帰って？

まずは再帰とは何かについて話していきます。再帰とは「ある関数の処理の中で自身を再度関数として呼び出す」ことを言います。言葉だと何のことかさっぱりだと思うので、例を出します。
ミンミンゼミの鳴き声を出力する関数を作成してみます。ミンミンゼミの鳴き声は「ミンミンミンミーン」のように鳴くことを前提とします。この鳴き方の特徴は

1. 「ミン」を連続して出力する
2. 最後は「ミーン」と出力する

と分解できます。それではサンプルコードを見ていきましょう。

package main

import "fmt"

func minmin(count int64) string {
	if count <= 0 {
		return "ミーン"
	} else {
		return "ミン" + minmin(count-1)
	}
}

func main() {
	fmt.Println(minmin(3)) // ミンミンミンミーン
}

minmin関数の中身を見ていきましょう。この関数の引数はcountで、これは何回「ミン」と鳴くかを指定します。
処理の初めにif count <= 0という条件があります。これはベースケースと呼ばれるもので、この条件に当てはまると再帰を終えるというものです。いわゆる終了条件で、ベースケースがないと永遠に処理が終わらない無限ループに陥り、場合によっては処理が異常終了してしまいます。引数がどんな値になったら処理を終了するのかを考え、ベースケースとして記載することを忘れないようにしてください。
ベースケース以外の場合、return "ミン" + minmin(count-1)に入ります。これは再帰呼び出しと呼ばれるもので、minmin関数の中で再度minmin関数を呼び出しています。この部分が再帰のポイントです。この呼び出しを可能にしているのが、コールスタックと呼ばれるメモリ構造です。コールスタックとは、関数呼び出しで使われるメモリ内の構造です。プログラム内で関数が呼ばれるとコールスタックに関数がPUSHし、関数の実行が終わるとコールスタックからPOPされ、戻り値を返します^[1]。
このように、ある処理を連続して実行するために自身の関数を呼ぶ処理のことを再帰と呼びます。

再帰が実行されるとどのような動きをするのか

再帰関数が実行されるとどのような動きをするか、詳細をみていきましょう。minmin(3)は、引数が3でベースケースの条件である0以下ではないため、関数の実行結果として"ミン" + minmin(2)を返します。この中にminmin(2)が呼ばれているので、コールスタックにPUSHします。イメージとしては以下です。

次に、コールスタックにPUSHされた"ミン" + minmin(2)をみます。式を見ると、1つのオペランド"ミン"と2つの演算子「+」と「minmin(2)」で評価しようとしています。ここでちょっと寄り道して、演算子の優先順位について解説します。この式の中で、演算子として扱うのは「+」と「minmin(2)」です。関数も演算子として扱うことに注意してください。そして、「+」演算子と関数のどちらが優先順位が高いかというと、関数です。関数は他のほとんどの演算子よりも優先順位が高い演算子なのです！なので、ここではminmin(2)が先に評価されます。なので先に評価されるminmin(2)を見てみましょう。引数が2で、ベースケースが0以下なので再度return処理が実行されます。この時"ミン" + minmin(1)が返されます。ここでもminmin(1)が呼ばれているので、コールスタックにPUSHします。

コールスタックにPUSHした"ミン" + minmin(1)をみていきます。先程述べた通り、関数が優先されて実行されるため、この式はminmin(1)が先に評価されます。minmin(1)は、引数が1で、これまたベースケースではないためreturn処理が実行されます。この時"ミン" + minmin(0)が返されます。minmin(0)が呼ばれているのでコールスタックにPUSHします。

コールスタックにPUSHした"ミン" + minmin(0)をみていきます。この式ではminmin(0)が先に評価されます。minmin(0)は、引数が0で、ベースケースに入るので、return "ミーン"が評価されます。これで関数呼び出しが終了しました。今のコールスタックの状態は以下です。

ここからはコールスタックに積まれた関数が上から順番に評価されていきます。一番上にあるのはminmin(0)の評価結果である"ミーン"です。これはすでに評価も終わっているので、POPされます。 POPされた後、次に積まれているminmin(0)に"ミーン"を代入します。

これで、"ミン" + minmin(0)が"ミン" + "ミーン"になりました。次は「+」演算子の評価が動きます。これは単純に"ミン"と"ミーン"を結合するだけなので、評価した結果は"ミンミーン"となります。これにて式の評価が完了したのでPOPされ、次に積まれているminmin(1)に"ミンミーン"を代入します。

"ミン" + minmin(1)が"ミン" + "ミンミーン"になりました。同じように「+」演算子の評価が動き、結果は"ミンミンミーン"となります。式の評価が完了したのでPOPされ、次に積まれているminmin(2)に"ミンミンミーン"を代入します。

"ミン" + minmin(2)が"ミン" + "ミンミンミーン"になりました。評価結果は"ミンミンミンミーン"となり、minmin(3)の実行結果としてPOPされます。

おわりに

最後まで見ていただきありがとうございます！感想や誤字脱字、認識の誤りなどございましたら遠慮なくコメントに記載いただけると嬉しいです。記事を書くモチベーションにつながるので是非お願いいたします。
次回も引き続き再帰について触れていきます。再帰を効率よく書くための方法について触れていく予定なので興味がある方は記事を見ていただけると幸いです。
それではまた次回お会いしましょう。アディオス！

脚注

1. PUSHやPOPについては後ほど作成するスタックの記事にて詳しく説明します。