Рекурсия в Go

В программировании есть такое понятие, как рекурсия: функция вызывает сама себя. На каждом шаге задача становится чуть меньше, пока не останется простой случай без нового вызова. Без такой остановки вызовы пойдут бесконечно.

Выведем с помощью рекурсии числа от 1 до 10. Номер шага передают параметром, а не хранят снаружи функции:

package main

import "fmt"

func show(i int) {
	fmt.Println(i)
	if i < 10 {
		show(i + 1) // функция вызывает сама себя
	}
}

func main() {
	show(1)
}

Сначала на экран попадает 1, затем функция вызывает себя с 2 и так далее. Когда i доходит до 10, условие ложно и новый вызов не делается. Если убрать if, остановки не будет.

Сумму чисел от 1 до n можно описать через сумму до n - 1 плюс само n. Для нуля сразу возвращают ноль, без нового вызова:

package main

import "fmt"

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

func main() {
	fmt.Println(func(4)) // выведет 10
}

Факториал задают тем же шаблоном. Для типа int аргумент не стоит брать больше 12: более крупное произведение может не поместиться в этот тип.

package main

import "fmt"

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

func main() {
	fmt.Println(fact(5)) // выведет 120
}

Параметром можно передать и срез. Каждый следующий вызов получает хвост без первого элемента, пока срез не станет пустым:

package main

import "fmt"

func show(nums []int) {
	if len(nums) == 0 {
		return
	}
	fmt.Println(nums[0])
	show(nums[1:])
}

func main() {
	show([]int{1, 2, 3})
}

На экране три строки: 1, 2 и 3. Тот же перебор чаще пишут циклом. Здесь срез нужен только чтобы увидеть, как рекурсия уменьшает параметр.

Дан срез:

nums := []int{1, 2, 3, 4, 5}

С помощью рекурсии выведите элементы этого среза на экран.

Напишите функцию func с базой для 0 и выведите результат для 5.

Напишите функцию fact с базой 1 и выведите факториал 4. Аргумент типа int не берите больше 12.