Как определить глубину рекурсии моей функции

Question

И снова с рекурсией. На этот раз пытаюсь понять, как определять глубину рекурсии

Задача: на ввод подается последовательность из натуральных чисел, нужно определить среднее этой последовательности.

Условие: Использовать только рекурсию.

Мое решение:

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 ситуация не лучше...

Answer 1

На моём компиляторе стек в вашей программе переполняется:

$ seq 10000000 -1 0 | go run temp.go
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow
...

Это видно и по потреблению памяти в мониторе. С оптимизированной хвостовой рекурсией память не должна расти. А она растёт.

Если оставаться в рамках линейной рекурсии, стек нельзя подчистить. Можно переделать в древовидную. Программа будет страшная (или красивая - кому как) но будет использовать логарифмический от количества чисел размер стека. Глубины стека в 500 рекурсивных вызовов хватит до тепловой смерти вселенной.
Ваша попытка сделать рекурсию неоптимизируемой повеселит компилятор, но ничего не изменит. Можно сделать так:

package main

import "fmt"

func main() {
    sum, count := rec()
    fmt.Printf("%f", sum / count)
}

func rec() (float64, float64) {
    x := 0.0
    fmt.Scan(&x)
    if x == 0 {
        return 0, 0
    }
    sum, count := rec()
    return sum + x, count + 1
}

P.S. Вычисление среднего через древовидную рекурсию. Переполнить стек нереально.

package main

import "fmt"

func treeRec(depth int) (bool, float64, int) {
    if depth == 0 {
        x := 0.0
        fmt.Scan(&x)
        if x == 0 {
            return true, 0, 0
        }
        return false, x, 1
    }
    done1, sum1, count1 := treeRec(depth - 1)
    if done1 {
        return done1, sum1, count1
    }
    done2, sum2, count2 := treeRec(depth - 1)
    return done2, sum1 + sum2, count1 + count2
}

func linearRec(depth int) (float64, int) {
    done, sum1, count1 := treeRec(depth)
    if done {
        return sum1, count1
    }
    sum2, count2 := linearRec(depth + 1)
    return sum1 + sum2, count1 + count2
}

func main() {
    sum, count := linearRec(0)
    fmt.Printf("%f", sum / float64(count))
}

P.P.S Не воспринимайте этот код серьезно. Да, хорошо что есть средства, которые позволяют работать с рекурсией в языках без оптимизации хвостовой рекурсии. Но, нет, никто так не делает на практике. Это лишь упражнение для вашего ума. На Go вместо линейной рекурсии пишите цикл и всё будет хорошо.

БЛОГ НА HUSL

Как определить глубину рекурсии моей функции

Ответы (1 шт):