Go言語の再帰関数

再帰は、関数が直接的または間接的に自身を呼び出すプログラミング技術です。

再帰関数には通常、次の2つの部分が含まれます:

  1. 基本条件(ベースケース):これは再帰の終了条件であり、関数が無限に自身を呼び出すことを防ぎます。
  2. 再帰条件(リカーシブケース):これは関数が自身を呼び出す部分であり、問題をより小さな部分問題に分解するために使用されます。

Go言語では、再帰の使用は他の言語と似ていますが、Goのいくつかの特性に注意する必要があります。

構文の形式は次のとおりです:

func recursion() {
   recursion() /* 関数が自身を呼び出す */
}

func main() {
   recursion()
}

Go言語は再帰をサポートしていますが、再帰を使用する際、開発者は終了条件を設定する必要があります。設定しないと、再帰は無限ループに陥ります。

再帰関数は、階乗の計算やフィボナッチ数列の生成など、数学的な問題を解決するのに非常に役立ちます。


階乗

階乗は正の整数の積であり、n!と表されます。例えば:

5! = 5 * 4 * 3 * 2 * 1 = 120

次の例では、Go言語の再帰関数を使用して階乗を実装します:

例

package main

import "fmt"

// 再帰関数で階乗を計算
func factorial(n int) int {
    // 基本条件
    if n == 0 {
        return 1
    }
    // 再帰条件
    return n * factorial(n-1)
}

func main() {
    fmt.Println(factorial(5)) // 出力: 120
}

コードの説明

  1. 基本条件:n がn0 に等しい場合、関数は 1 を返します。なぜなら0!0! は 1 と定義されているからです。
  2. 再帰条件:関数はnに ~ を掛けたfactorial(n-1)結果を返し、問題を徐々に小さな部分問題に分解します。

上記の例を実行した出力結果は次のとおりです:

120

フィボナッチ数列

次の例では、Go言語の再帰関数を使用してフィボナッチ数列を実装します:

例

package main

import "fmt"

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

func main() {
    var i int
    for i = 0; i < 10; i++ {
       fmt.Printf("%d\t", fibonacci(i))
    }
}

上記の例を実行した出力結果は次のとおりです:

0    1    1    2    3    5    8    13    21    34

平方根を求める

次の例は、Go言語で再帰メソッドを使用して平方根を求めるコードです:

例

package main

import (
        "fmt"
)

func sqrtRecursive(x, guess, prevGuess, epsilon float64) float64 {
        if diff := guess*guess - x; diff < epsilon && -diff < epsilon {
                return guess
        }

        newGuess := (guess + x/guess) / 2
        if newGuess == prevGuess {
                return guess
        }

        return sqrtRecursive(x, newGuess, guess, epsilon)
}

func sqrt(x float64) float64 {
        return sqrtRecursive(x, 1.0, 0.0, 1e-9)
}

func main() {
        x := 25.0
        result := sqrt(x)
        fmt.Printf("%.2f の平方根は %.6f\n", x, result)
}

上記の例では、sqrtRecursiveこの関数は再帰方式を使用して平方根の計算を実装しています。

sqrtRecursiveこの関数は4つのパラメータを受け取ります:

  • x平方根を求めたい数値を表します
  • guess現在の推定平方根値を表します
  • prevGuess前回の推定値を表します
  • epsilon精度要件(平方根への近さの程度)を表します

再帰の終了条件は、現在の推定平方根と前回の推定平方根が非常に近く、その差が指定された精度 epsilon 未満であることです。

sqrt 関数では、sqrtRecursive を呼び出して平方根を計算し、初期値と精度要件を渡します。次に、main 関数では sqrt 関数を呼び出して平方根を求め、結果を出力します。

上記のコードを実行した出力結果は次のとおりです:

25.00 的平方根为 5.000000

再帰の長所と短所

長所

  • 簡潔さ:再帰コードは通常、反復コードよりも簡潔で理解しやすいです。
  • 問題の分解:再帰は、木の走査や分割統治法など、類似した部分問題に分解できる問題の解決に自然に適しています。

短所

  • パフォーマンスのオーバーヘッド:再帰呼び出しはスタック領域を消費し、特に深い再帰の場合、スタックオーバーフローを引き起こす可能性があります。
  • デバッグの難しさ:再帰コードは、特に再帰の深さが大きい場合、デバッグが難しい可能性があります。

再帰と反復

再帰と反復は、問題を解決するための2つの異なる方法です。再帰は関数が自身を呼び出すことで問題を解決しますが、反復はループ構造(例えばforループ)を使用してコードブロックを繰り返し実行します。

再帰 vs 反復

特性 再帰 反復
コードの簡潔さ 通常はより簡潔 より冗長になる可能性がある
パフォーマンス 遅くなる可能性があり、スタック領域を消費する 通常はより速く、メモリ消費が少ない
適用シーン 部分問題に分解できる問題に適している 線形または単純な反復問題に適している

再帰の一般的な応用

再帰は多くのアルゴリズムやデータ構造で広く応用されています。例えば:

  • 木とグラフの走査:深さ優先探索(DFS)など。
  • 分割統治法:マージソート、クイックソートなど。
  • 動的計画法:フィボナッチ数列の計算など。

ファイルディレクトリの走査

例

import (
    "fmt"
    "os"
    "path/filepath"
)

func walkDir(dir string, indent string) {
    entries, err := os.ReadDir(dir)
    if err != nil {
        return
    }

    for _, entry := range entries {
        fmt.Println(indent + entry.Name())
        if entry.IsDir() {
            walkDir(filepath.Join(dir, entry.Name()), indent+"  ")
        }
    }
}

func main() {
    walkDir(".", "")
}

Goで再帰を使用する場合は、基本条件(終了条件)の正確性に特に注意し、無限再帰を避ける必要があります。パフォーマンスに敏感な場面や深い再帰が発生する可能性がある場面では、反復実装や channel/goroutine などのGo固有のメカニズムを検討することをお勧めします。

その他の拡張