Go言語の再帰関数の基本！再帰処理の書き方と例

先生と生徒の会話形式で理解しよう

生徒

「Go言語で、同じ処理を何回も繰り返すにはどうしたらいいですか？」

先生

「同じ処理を繰り返したいときは、繰り返し文（ループ）か、関数を自分自身で呼び出す“再帰関数”という方法があります。」

生徒

「関数を自分自身で呼び出すって、どういうことですか？」

先生

「それが“再帰（さいき）”と呼ばれる処理です。具体的に見ていきましょう。」

1. Go言語の再帰関数とは？

Go言語の再帰関数（さいきかんすう）とは、関数の中で自分自身をもう一度呼び出すように書かれた関数のことです。あたかも「自分に同じ仕事をもう一度お願いする」ようなイメージで、同じような処理を少しずつ条件を変えながら繰り返したいときに使います。

通常はfor文などのループを使って繰り返し処理を書きますが、処理の流れを分かりやすくしたいときや、分割して考えたいときには再帰関数が役に立ちます。複雑な問題でも、「小さな同じ形の問題」に分けて考えられるので、Go言語のアルゴリズムではよく使われる書き方です。

例えば、「1から5までの合計を求める」という処理を考えてみましょう。普通に書くと1＋2＋3＋4＋5と並べますが、再帰的に考えると「1から5までの合計＝5＋（1から4までの合計）」というように、同じ形の問題に分けて考えることができます。


func sum(n int) int {
    if n == 1 {
        return 1
    }
    return n + sum(n-1)
}

func main() {
    result := sum(5)
    fmt.Println(result)
}

このサンプルでは、sumという関数が自分自身のsumを呼び出しているところが再帰のポイントです。nが1のときだけはそれ以上呼び出さずに1を返し、それ以外のときはn + sum(n-1)として、ひとつ小さい数に問題を渡しています。こうすることで、「1から5までの合計」の中に「1から4までの合計」「1から3までの合計」…といった同じ形の問題が連鎖していき、最終的に1にたどり着いたところで、計算結果が逆順に戻ってきて答えが完成します。

このように、再帰関数は「自分自身を呼び出す関数」であり、Go言語で繰り返し処理を考えるときの、もうひとつの選択肢だと覚えておくと理解しやすくなります。

2. Go言語で再帰関数を書く基本構文

ここでは、Go言語で再帰関数を書くときの基本的な形を確認しておきましょう。再帰関数は少し不思議に見えますが、「決まりごと」を押さえてしまえば、どの再帰処理も同じパターンで書けるようになります。

再帰関数は大きく分けて、次の3つのパーツからできています。

関数の宣言：関数名・受け取る値（引数）・返す値（戻り値）を決める部分
終了条件（ベースケース）：これ以上自分自身を呼び出さない条件
自分自身を呼び出す部分：同じ関数を少しだけ状態を変えて呼び出す部分

この3つを意識すると、再帰関数の基本構文は次のように書けます。


func functionName(n int) int {
    if n <= 1 {        // ② 終了条件（ベースケース）
        return 1
    }
    // ③ 自分自身を呼び出す「再帰呼び出し」
    return n * functionName(n-1)
}

最初のfunc functionName(n int) intが関数の宣言です。ここでは、nという整数を受け取り、整数を1つ返す関数だということを表しています。

if n <= 1 { return 1 }の部分が終了条件（ベースケース）です。「もうこれ以上は自分自身を呼び出さずに、ここで答えを返して終わる」と決める場所だと思ってください。この終了条件がないと、延々と自分自身を呼び出し続けてしまい、プログラムが止まらなくなります。

最後のreturn n * functionName(n-1)が再帰呼び出しの部分です。自分と同じfunctionNameをもう一度呼び出していますが、nの値をひとつ小さくして渡している点がポイントです。毎回少しずつ問題を小さくしていき、いつかn <= 1の条件にたどり着くようにしています。

もう少し直感的な例として、「カウントダウン」を行う簡単な再帰関数を見てみましょう。画面に3, 2, 1と表示してから「スタート！」と表示するだけの、イメージしやすいサンプルです。


func countdown(n int) {
    if n == 0 {                 // 0まで来たら終了
        fmt.Println("スタート！")
        return
    }
    fmt.Println(n)              // 現在の数字を表示
    countdown(n-1)              // ひとつ小さい数字で自分自身を呼び出す
}

func main() {
    countdown(3)
}

このcountdown関数でも、やっていることは先ほどと同じです。n == 0のときに処理を終える終了条件があり、それ以外のときはcountdown(n-1)で自分自身を呼び出すことで、3 → 2 → 1 → 0と少しずつゴールに近づいていきます。

このように、Go言語の再帰関数は「終了条件」と「自分自身を呼び出す処理」をセットで考えるのがコツです。この基本構文に慣れておくと、次に出てくるフィボナッチ数列のような、少し複雑な再帰処理も理解しやすくなります。

3. フィボナッチ数列を再帰関数で計算してみよう

フィボナッチ数列とは、次のような数列です：

0, 1, 1, 2, 3, 5, 8, 13, 21, ...（前の2つの数字を足した数が次になる）

これを再帰関数で求めるには、次のように書きます。


func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

fibonacci関数は、引数nに対して、nが1以下ならnをそのまま返し、そうでない場合は、fibonacci(n-1)とfibonacci(n-2)を足して返します。

4. 実際に使ってみよう：再帰関数で階乗（factorial）を計算

階乗とは、ある整数までのすべての整数をかけ算した結果のことです。たとえば、5の階乗（5!）は、5 * 4 * 3 * 2 * 1になります。


func factorial(n int) int {
    if n == 0 {
        return 1
    }
    return n * factorial(n - 1)
}

func main() {
    result := factorial(5)
    fmt.Println(result)
}

このように、関数の中で同じ関数を繰り返し呼び出すことで、計算を段階的に進めることができます。

5. 再帰関数を使うときの注意点

再帰関数を使うときは、次の2点に気をつけましょう：

終了条件（ベースケース）を必ず書くこと：これがないと、関数が無限に呼び出されてしまい、プログラムが止まりません。
呼び出しが深くなりすぎると、メモリをたくさん使う：たとえば、fibonacci(50)など、大きな数字を使うとパソコンの処理が重くなることがあります。

基本をしっかり理解して使えば、再帰関数はとても便利なテクニックです。

まとめ

Go言語の再帰関数は、複雑な繰り返し処理を直感的でわかりやすい形にできる非常に便利な仕組みであり、基本的な構造や終了条件の重要性を理解することで幅広いアルゴリズムに応用できます。とくに階乗計算やフィボナッチ数列のように、ひとつ前の計算結果を基に次の値を導き出す処理は再帰と相性が良く、処理の流れを視覚的に把握しやすくなるという利点があります。再帰関数を書くときは、無限ループを防ぐ終了条件を必ず設定すること、そして処理が深くなりすぎるとスタック領域を多く消費する性質があるため、実行時の負荷を考えながら使う必要があります。また、関数を自分自身で呼び出すという構造は、木構造の探索や分割統治法など、より高度なアルゴリズムにも応用される基礎的な概念です。学びを進めるうえで、簡単な再帰処理から徐々にステップアップし、より複雑なデータ構造やアルゴリズムに触れていくことで、Go言語のプログラム設計力が大きく向上します。再帰は慣れるまで難しく感じることもありますが、基本を押さえれば強力な武器になります。ここでは、再帰の考え方をより深く理解できるよう、同じクラス名やタグ構造を利用しながらサンプルコードを掲載し、実際の使い方をイメージしやすいように工夫しています。

再帰の流れを理解するためのサンプルプログラム


package main

import "fmt"

func sumTo(n int) int {
    if n == 1 {
        return 1
    }
    return n + sumTo(n-1)
}

func main() {
    result := sumTo(10)
    fmt.Println(result)
}

上記のサンプルでは、10までの合計を再帰処理で求めています。終了条件として「n が 1 になったら 1 を返す」という基準を定め、それ以外の場合は n と sumTo(n-1) を足し合わせる形で計算を進めています。このように、再帰は「最終的にどこで止まるか」を明確に決め、その条件に向けて段階的に値を縮めていくという流れが基本になります。再帰関数を実際に動かしてみると、処理が少しずつ積み重なり、最終的に一つの答えになるという仕組みがより理解しやすくなるでしょう。また、Go言語で再帰処理を書く場合は、スタックの消費やパフォーマンスの特性も理解しておくと、アルゴリズム設計の幅が大きく広がります。フィボナッチ数列のように計算量が急増する処理では、メモ化やループへの書き換えなどを使って負荷を軽減する方法もあります。こうした最適化の考え方も、再帰処理の理解を深めるために重要なポイントとなります。

先生と生徒の振り返り会話

生徒

「きょう学んだ再帰関数って、同じ関数を呼び出していくところが面白かったです。でも、どこで止めるか考えないと無限に続いちゃうんですね。」

先生

「そうなんだ。終了条件がとても大事だよ。再帰は便利だけれど、止まる条件を間違えるとプログラムが止まらなくなるからね。」

生徒

「フィボナッチ数列や階乗の例も分かりやすかったです。再帰で書くとシンプルになるんですね。」

先生

「うん、再帰は構造をシンプルにできるところが魅力だよ。ただし計算量が増えるケースでは注意しないといけないから、状況によって最適化やループへの置き換えも必要になるんだ。」

生徒

「なるほど。再帰はちゃんと使いどころを見極めるのが大事なんですね。」

先生