两个函数的无限计算
Infinite Computation of two functions
我有以下两个功能
let rec f n =
if n < 10 then "f" + g (n + 1) else "f"
and g n =
if n < 10 then "g" + f (n + 1) else "g"
我需要找出 f 是否有任何参数可以启动无限计算。
我的直接回答是否定的，因为上限是 10，这总是 return 一个字母。这个对吗？
我假设第 2 行和第 4 行应该缩进，否则这不是有效的 F#。
理论上
g和f除了输出是一样的，我们不关心输出。所以我们不妨看看下面的函数，它具有相同的终止属性但丢弃了输出：
let rec f n = if n < 10 then f (n + 1)
f 的输入类型是 int，这是一个 32 位有符号整数。它只允许从 -2147483648 到 2147483647（System.Int32.MinValue 和 System.Int32.MaxValue）的值。没有其他有代表性的案例。
好吧，任何 10 或更高的输入都会终止，否则只会累加直到达到 10 然后终止。
实践中
也就是说，问题中的函数连接字符串的方式具有 O(n²) 时间复杂度。我认为您不想等待 f System.Int32.MinValue 这样的调用在真实计算机上终止。此外，这些不是尾递归的。您肯定会耗尽筹码或时间限制。所以这是一个在现实中没有用的理论属性的案例。
换句话说：嗯，你到底在做什么？
我有以下两个功能
let rec f n =
if n < 10 then "f" + g (n + 1) else "f"
and g n =
if n < 10 then "g" + f (n + 1) else "g"
我需要找出 f 是否有任何参数可以启动无限计算。
我的直接回答是否定的，因为上限是 10，这总是 return 一个字母。这个对吗？
我假设第 2 行和第 4 行应该缩进，否则这不是有效的 F#。
理论上
g和f除了输出是一样的，我们不关心输出。所以我们不妨看看下面的函数，它具有相同的终止属性但丢弃了输出：
let rec f n = if n < 10 then f (n + 1)
f 的输入类型是 int，这是一个 32 位有符号整数。它只允许从 -2147483648 到 2147483647（System.Int32.MinValue 和 System.Int32.MaxValue）的值。没有其他有代表性的案例。
好吧，任何 10 或更高的输入都会终止，否则只会累加直到达到 10 然后终止。
实践中
也就是说，问题中的函数连接字符串的方式具有 O(n²) 时间复杂度。我认为您不想等待 f System.Int32.MinValue 这样的调用在真实计算机上终止。此外，这些不是尾递归的。您肯定会耗尽筹码或时间限制。所以这是一个在现实中没有用的理论属性的案例。
换句话说：嗯，你到底在做什么？