Go/再帰的関数呼出し

再帰的関数呼出し

Goの関数は、再帰的関数呼出し(recursive function call)が可能です。

再帰的関数呼出し

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func strd(i int) string {
	if i < 0 {
		return "-" + strd(-i)
	}
	result := ""
	up := i / 10
	if up > 0 {
		result += strd(up)
	}
	d := i % 10
	return result + string("0123456789"[d])
}
func main() {
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < 10; i++ {
		x := rand.Intn(1000000) - 500000
		s1, s2 := strd(x), fmt.Sprintf("%d", x)
		fmt.Println(s1 == s1, s1, s2)
	}
}

結果(例)

true -483212 -483212
true 319615 319615
true 210968 210968
true 7121 7121
true -465444 -465444
true -26256 -26256
true -122926 -122926
true 474282 474282
true -492355 -492355
true 180083 180083

strd()は、11行目と16行目で自分自身を呼び出しています。

フィボナッチ数

再帰的関数呼出しの定番、フィボナッチ数。

フィボナッチ数

package main

import "fmt"

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

func main() {
	for i := 0; i < 41; i++ {
		fmt.Println(i, fibo(i))
	}
}

結果

0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
17 1597
18 2584
19 4181
20 6765
21 10946
22 17711
23 28657
24 46368
25 75025
26 121393
27 196418
28 317811
29 514229
30 832040
31 1346269
32 2178309
33 3524578
34 5702887
35 9227465
36 14930352
37 24157817
38 39088169
39 63245986
40 102334155