Hike News
Hike News

Go初識-day9-遞歸函數

Golang 本文总阅读量次

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

Golang