再帰を構成するには、次の条件を満たす必要があります。
- 問題は複数のサブ問題に分割できます。
- 分割前の元の問題と分割後の副問題はデータ規模を除いて異なりますが、問題を処理する考え方は同じです。
- それ自体を無制限に呼び出すことはできず、部分問題には再帰状態を終了するための条件が必要です。
注: 再帰関数を作成する場合は、終了条件が必要です。そうでないと、メモリがオーバーフローするまで無限に呼び出されます。
ここでは、再帰関数の使用法を示すいくつかの例を示します。
フィボナッチ数列
Go 言語で記述された再帰関数を通じてフィボナッチ数列を出力する方法を示すために、再帰関数の古典的な例であるフィボナッチ数列を例として取り上げてみましょう。
配列の形式は次のとおりです。
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …
Go 言語の再帰関数を使用してフィボナッチ数列を実装する具体的なコードは次のとおりです。
package main
import "fmt"
func main() {
result := 0
for i := 1; i <= 10; i++ {
result = fibonacci(i)
fmt.Printf("fibonacci(%d) is: %d\n", i, result)
}
}
func fibonacci(n int) (res int) {
if n <= 2 {
res = 1
} else {
res = fibonacci(n-1) + fibonacci(n-2)
}
return
} 出力は次のとおりです。
fibonacci(1) is: 1
fibonacci(2) is: 1
fibonacci(3) is: 2
fibonacci(4) is: 3
fibonacci(5) is: 5
fibonacci(6) is: 8
fibonacci(7) is: 13
fibonacci(8) is: 21
fibonacci(9) is: 34
fibonacci(10) is: 55
階乗数
正の整数の階乗はその数値以下のすべての正の整数の積であり、0 の階乗は 1 であり、自然数 n の階乗はn!と書き、「キストン・カマン」がn!を発明しました。 1808 n!この演算子記号。
たとえば、 n!=1×2×3×…×n 、階乗は0!=1，n!=(n-1)!×nように再帰的に定義することもできます。
再帰関数を使用して、指定された数値の階乗を計算します。サンプル コードは次のとおりです。
package main
import "fmt"
func Factorial(n uint64) (result uint64) {
if n > 0 {
result = n * Factorial(n-1)
return result
}
return 1
}
func main() {
var i int = 10
fmt.Printf("%d の階乗は %d\n", i, Factorial(uint64(i)))
} 出力は次のとおりです。
10 の階乗は 3628800
相互に呼び出し合う再帰関数は Go 言語でも使用できます。複数の関数が相互に呼び出して閉ループを形成します。Go 言語コンパイラーの特殊性により、これらの関数の宣言順序は任意です。次の簡単な例は、関数奇数と偶数の間の相互呼び出し:
package main
import (
"fmt"
)
func main() {
fmt.Printf("%d is even: %t\n", 16、even(16)) // 16は偶数です：真
fmt.Printf("%d is odd: %t\n", 17、odd(17))
// 17は奇数です：true
fmt.Printf("%d is odd %t\n", 18、odd(18))
// 18は奇数です：false
}
func even(nr int) bool {
if nr == 0 {
return true
}
return odd(RevSign(nr) - 1)
}
func odd(nr int) bool {
if nr == 0 {
return false
}
return even(RevSign(nr) - 1)
}
func RevSign(nr int) int {
if nr < 0 {
return -nr
}
return nr
} ランニング効果は以下の通りです。
16 is even: is true
17 is odd: is true
18 is odd: is false