2 / 3

Parašyk factorial — rekursija ir ciklas greta

Šiam eksperimentui neliesk savo programos — susikurk atskirą aplanką (mkdir rekursija, viduje go mod init rekursija) ir sukurk main.go.

Abu variantai greta — 1 žingsnio popierinis sekimas, tik kodu:

factorial — rekursinis: bazinis atvejis n <= 1 (ne n == 1 — taip factorial(0) irgi saugus), rekursinis atvejis n * factorial(n-1).
factorialLoop — tas pats darbas paprastu for ciklu: trumpesnis, be dėklo augimo.

Patikrink — go run . turi išvesti lygiai:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
loop says: 120

Abu keliai duoda 120 — skiriasi tik kelias.

Spąstai. Ištrink bazinį atvejį (arba pamiršk mažinti — parašyk factorial(n) vietoje factorial(n-1)) ir paleisk. Kvietimai nebeturi kur sustoti, dėklas auga, kol Go pasiduoda:
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow
Įsidėmėk šitą žinutę — stack overflow beveik visada reiškia rekursiją be veikiančio bazinio atvejo. Bazinis atvejis privalo (a) egzistuoti ir (b) būti pasiekiamas — kiekvienas kvietimas turi mažinti užduotį. Grąžink n-1 atgal ir įsitikink, kad vėl veikia.

main.go SUKURTI

Sukurk šį failą kataloge ./

package main

import "fmt"

// factorial computes n! recursively: the base case stops the calls,
// the recursive case shrinks the problem by one.
func factorial(n int) int {
	if n <= 1 { // base case — without it the calls would NEVER stop
		return 1
	}
	return n * factorial(n-1) // recursive case — a SMALLER problem
}

// factorialLoop computes the same n! with a plain loop — Go's default tool.
func factorialLoop(n int) int {
	result := 1
	for i := 2; i <= n; i++ {
		result *= i
	}
	return result
}

func main() {
	for n := 1; n <= 5; n++ {
		fmt.Printf("%d! = %d\n", n, factorial(n))
	}
	fmt.Println("loop says:", factorialLoop(5))
}