再帰はプログラミング言語における重要な概念の1つです。
この記事では、Goで再帰を使用する方法を解説します。
再帰とは
再帰とは、ある関数が自分自身を呼び出すこと、つまり再帰することです。
プログラム内の関数が自分自身を呼び出すと、再帰が発生します。
再帰性の基準
再帰的な関数であるためには、いくつかの定義された条件を満たす必要があります。以下はその例である。
- 関数が自分自身を呼び出す
- 停止条件がある
この法則に従わない関数を無限再帰関数と呼ぶことができます。
再帰の種類
上記で説明したように、再帰には2つのタイプがあります。
一つは有限または規則的な再帰で、もう一つは無限再帰です。それぞれの特徴について見ていきましょう。
有限再帰
有限再帰、または単に再帰とは、関数が以下の状態にあることです。
- 関数が自分自身を呼び出す
- 停止条件がある
以下は、有限再帰の例です。
package main
import (
"fmt"
)
func recurFact(i int) int {
if i == 0 {
return 1
} else {
return i * recurFact(i - 1)
}
}
func main() {
num := recurFact(20)
fmt.Println(num) // 2432902008176640000
}無限再帰
無限再帰は、以下の2番目の条件が守られていない場合に起こります。簡単に言うと、関数が自分自身を呼び出すのを止めないということです。
- 関数が自分自身を呼び出す
- 停止条件がある
以下は、無限再帰のコード例です。
package main
import (
"fmt"
)
func recurse() {
fmt.Println("Endless!!!")
recurse()
}
func main() {
// recurse() // 永遠に呼び出す
}再帰メソッド
再帰は呼び出す方法や順序が異なるため、2種類に分類される。
1つは通常の方法で、もう1つは末尾再帰的な方法です。それぞれについて見てみましょう。
通常の再帰
通常の再帰は、呼び出し自体がすぐに計算を終了せず、階層を下って計算を行うことです。
以下はそのコード例です。
package main
import (
"fmt"
)
func fib(i int) int {
if (i == 0) {
return 0
} else if(i == 1) {
return 1
} else {
return fib(i - 1) + fib(i - 2)
}
}
func main() {
fmt.Println(fib(20)) // 6765
}末尾再帰
末尾再帰は自分自身を呼び出す関数が値を計算し、その値を階層を下って送信するときに起こります。
以下は末尾再帰のコード例である。
package main
import (
"fmt"
)
func f(i int) {
if(i == 0) {
fmt.Println("Zero")
return
} else {
fmt.Println(i)
f(i-1) // 末尾から呼び出し
}
}
func main() {
f(3)
// 出力結果:
// 3
// 2
// 1
// Zero
}末尾再帰のメリット
末尾呼び出しは多くの場合、コンパイラによって最適化されるという点でメリットがあります。
そのためほとんどの場合、通常の再帰呼び出しよりも高速になります。
関数の種類
再帰には、通常の関数と無名関数のどちらのタイプの関数も使用することができます。
通常の関数の場合
以下は、再帰性を示す通常の関数のコード例です。
package main
import (
"fmt"
)
func f(i int) {
if(i == 0) {
return
} else {
fmt.Println(i)
f(i-1)
}
}
func main() {
f(5)
// 出力結果:
// 5
// 4
// 3
// 2
// 1
// Zero
}無名関数の場合
無名関数で再帰を実装するも可能です。以下は再帰性を示す無名関数のコード例です。
package main
import (
"fmt"
)
func main() {
var f func(int)
f = func(i int) {
if(i == 5) {
fmt.Println("終了")
return
} else {
fmt.Println(i)
f(i-1)
}
}
f(9)
// 出力結果:
// 9
// 8
// 7
// 6
// 終了
}
