0

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

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

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

Мое решение:

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

9
  • 3
    Глубина стека равна количеству чисел, верно. Некоторые компиляторы удаляют концевую рекурсию - у вас именно такая, но про компилятор go не знаю.
    – MBo
    20 ноя в 8:01
  • 3
    Если удаляет, то её вообще не будет, в скомпилированном коде тело функции превратится в цикл
    – MBo
    20 ноя в 8:04
  • 1
    Как увидеть в go - не знаю, промежуточного кода там же нет, только ассемблерный листинг смотреть. А условию удовлетворяет - вы код сделали с рекурсией, а дальше дело компилятора.
    – MBo
    20 ноя в 8:18
  • 2
    Глубина рекурсии != глубина стека. Глубина рекурсии - это абстрактная величина, равная максимальной длине цепочки вызовов. Глубина стека - это конкретная величина, которая очень сильно зависит от особенностей компилятора. Например, если компилятор умеет обрабатывать концевую рекурсию, то стек вообще расти не будет. Но на глубину рекурсии это не влияет.
    – Pak Uula
    20 ноя в 10:52
  • 1
    Тривиальные операции вроде 1 * компилятор выбросит. Если хотите испортить хвостовую оптимизацию, вычисления надо перенести из аргументов функции на её результат. 20 ноя в 13:01

1 ответ 1

2
  1. На моём компиляторе стек в вашей программе переполняется:
$ seq 10000000 -1 0 | go run temp.go
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow
...

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

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

  2. Ваша попытка сделать рекурсию неоптимизируемой повеселит компилятор, но ничего не изменит. Можно сделать так:

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 вместо линейной рекурсии пишите цикл и всё будет хорошо.

7
  • Странно. Читаю про древовидную рекурсию и написано, что она как раз больше вызовов делает и быстрее стэк переполняет. [here](studopedia.ru/29_79740_lineynaya-i-drevovidnaya-rekursii.html
    – Quester
    21 ноя в 8:41
  • 1
    @Quester, вы нашли плохую статью. Я с первого просмотра нашел две фактические ошибки. Одна про переполнение стека в древовидной рекурсии. 21 ноя в 10:43
  • да, я понимаю, что такие задачи необязательно решать через рекурсию(даже может быть нежелательно), но я пытаюсь разобраться в рекурсии, чтобы быть хорошим программистом и не впасть в ступор, когда столкнусь с древовидной рекурсией и хочу уметь в нее.
    – Quester
    21 ноя в 17:33
  • @Quester, знать и уметь хорошо, добро пожаловать в клуб. Технология сокращения глубины стека путем переделки рекурсии мне пригодилась два раза: тут и ещё раз тут в другом вопросе. 21 ноя в 17:41
  • А может вы знаете ресурс, где можно почитать хорошие статьи и другую инфу, чтобы научиться в рекурсию? сейчас слабо понимаю рекурсию, целый день сижу и пытаюсь врубиться в рекурсию в quickSort. Пока что врубился только в хвостовую рекурсию, а все остальное мне прям тяжело дается. А хотелось бы и в древовидную.
    – Quester
    21 ноя в 19:03

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.