主页 / 问题 / 1552185
Accepted
Quester
Asked:2023-11-20 15:42:53 +0000 UTC2023-11-20 15:42:53 +0000 UTC

如何确定函数的递归深度

  • 772

再次使用递归。这次我想弄清楚如何确定递归深度

问题：给出一个自然数序列作为输入；您需要确定该序列的平均值。

条件：仅使用递归。

我的决定：

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它会在每次调用后打印堆栈。这个结论是否意味着堆栈根本不臃肿？

更新：

根据评论，我去阅读了尾递归，发现了一个尾递归不会被优化的例子。

缺乏优化的示例

基于这个例子，我稍微编辑了我的代码，如下所示：

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也好不到哪里去…… 方案

golang

1 个回答

  1. Best Answer
    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
}

    PS通过树递归计算平均值。堆栈溢出是不可能的。

    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))
}

    PPS不要认真对待这段代码。是的，有一些工具可以让您在不优化尾递归的情况下使用语言中的递归，这很好。但实际上没有人这样做。这只是对你思维的一个练习。在Go中，不用线性递归，而是写一个循环，一切都会好起来的。

    • 2

相关问题