И снова с рекурсией. На этот раз пытаюсь понять, как определять глубину рекурсии
Задача: на ввод подается последовательность из натуральных чисел, нужно определить среднее этой последовательности.
Условие: Использовать только рекурсию.
Мое решение:
package main
import "fmt"
func main() {
fmt.Printf("%f", rec(0, 0))
}
func rec(sum, count float64) float64 {
x := 0.0
fmt.Scan(&x)
if x == 0 {
return sum / count
}
return rec(sum+x, count+1)
}
Задался вопросом, какова глубина рекурсии у моего решения. Предполагаю, что глубина рекурсии данной функции будет равна переменной count
. В таком случае, вижу потенциальное переполнение стека, если последовательность будет продолжаться бесконечно. Если мое прежположение вернО, то как подчищать стек после каждого вызова, чтобы он не раздувался?
Пытался сделать strace -k go run .
и при вводе чисел "1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,0" получаю вывод
> /usr/lib/go-1.21/bin/go() [0x70b63]
> /usr/lib/go-1.21/bin/go() [0xebe7]
> /usr/lib/go-1.21/bin/go() [0x4042c]
> /usr/lib/go-1.21/bin/go() [0x41d5c]
> /usr/lib/go-1.21/bin/go() [0x42b51]
> /usr/lib/go-1.21/bin/go() [0x43a66]
> /usr/lib/go-1.21/bin/go() [0x6cece]
+++ exited with 0 +++
Но не понимаю, что он значит. По идее -k
выводит стек после каждого вызова. Значит ли этот вывод, что стек все таки не раздувается?
UPD:
На основе ккомментариев пошел читать про хвостовую рекурсию и нашел такое пример, при котором хвостовая рекурсия не будет оптимизирована.
И на основе этого примера, слегка, отредактировал свой код до вида:
package main
import "fmt"
func main() {
fmt.Printf("%f", rec(0, 0))
}
func rec(sum, count float64) float64 {
x := 0.0
fmt.Scan(&x)
if x == 0 {
return sum / count
}
return 1 * rec(sum+x, count+1)
}
Сделало ли это рекурсию не оптимизируемой и как узнать, оптимизируется ли моя рекурсия до итерации?
UPPD
Начал читать sicp и там так же пишут(по мне вполне справедливо и обосновано), что древовидная рекурсия порождает кратно больше рекурсивных вызовов, чем даже линейная. На каких вообще данных древовидная рекурсия будет полезна? Не пойму что-то зачем же она нужна.
алгоритм древовидной рекурсии про который идет речь в абзаце на скрине выше:
и схема порождения вызовов в древовидной рекурсии. На ней видно что fib 1
вызывается аж 5 раз и с остальными fib x
ситуация не лучше...
1 *
компилятор выбросит. Если хотите испортить хвостовую оптимизацию, вычисления надо перенести из аргументов функции на её результат.