Go初識-day9-遞歸函數

introduction

一個函數調用了自己,就叫做遞歸

設計原則

  1. 一個大問題可拆分出多個邏輯相同的子問題
  2. 且問題的規模會不斷的縮小,最後收斂
  3. 定義好出口條件
  • 若沒有定義好出口條件,會造成死循環

無限循環

1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import (
"fmt"
"time"
)

func main(){
fmt.Println("Hello World")
time.Sleep(time.Second)
main()
return
}

result

1
2
3
4
5
6
7
Hello World
Hello World
Hello World
Hello World
Hello World
...
...

如果未設置退出遞歸的條件將無限循環下去


設置退出條件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main

import (
"fmt"
"time"
)

func recusive(n int){
fmt.Println("Hello World")
time.Sleep(time.Second)
if n > 5 {
return
}
recusive(n+1)
}

func main(){
recusive(0)
}

result

1
2
3
4
5
6
7
Hello World
Hello World
Hello World
Hello World
Hello World
Hello World
Hello World

階乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

import "fmt"

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

func main(){
for {
var input int
fmt.Printf("number >>")
fmt.Scanf("%d\n",&input)

result := multi(input)
fmt.Printf("%d! result :%d\n",input,result)

}
}

result

1
2
3
4
5
6
number >>3
3! result :6
number >>4
4! result :24
number >>5
5! result :120

斐波那契數列

返回的數為數列前兩數相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

import "fmt"

func Fibonacci(n int)int{
if n == 1 || n == 2 {
return 1
}
return Fibonacci(n-1) + Fibonacci(n-2)
}

func main(){
for {
var input int
fmt.Printf("number >>")
fmt.Scanf("%d\n",&input)

result := Fibonacci(input)
fmt.Printf("Fib(%d) result :%d\n",input,result)

}
}

result

1
2
3
4
5
6
7
8
number >>3
Fib(3) result :2
number >>4
Fib(4) result :3
number >>5
Fib(5) result :5
number >>6
Fib(6) result :8