判断递归函数是否收敛

Question

考虑下面的递归阶乘函数：

fact(n) =
    if (n = 0) return 1
    return n * fact(n - 1)

上面的函数对包括零在内的所有正整数都收敛。然而，对于负整数，它并不收敛。

接下来，考虑以下程序：

fact(n) =
    if (n < 0) return 0
    if (n = 0) return 1
    return n * fact(n - 1)

上面的函数对所有整数都是收敛的。

我想知道如何静态地确定递归函数是否收敛。

Answer 1

你没有指定语言并暗示你在考虑无界整数，这是一件好事，因为这意味着我可以向你推荐this prototype analyzer for a toy language作为一个web应用程序。

对于无界整数，rici是对的，这就是停顿问题。然而，静态分析器解决的大多数其他问题也等同于停止问题。这并不妨碍所讨论的静态分析器的使用。他们通过接受假阴性、假阳性或两者兼而有之来解决不可判断性问题。

如果您更喜欢使用类似C的语法，也可以使用Frama-C的值分析来确定whether a simple C program terminates。此分析器不处理递归函数，它将整数类型视为有界(它们确实是有界的)。有界整数类型在理论上使问题变得容易(对于输入语言的某些定义，它变得可判定)，但在实践中仍然很难。

Answer 2

你不能，在一般情况下。这个问题正是halting problem提出的。

下面是一个递归函数的简单示例，它可能会在所有正输入时终止，以尾递归方式编写(断言对所有正n都会停止的断言是Collatz conjecture)：

stop(n, a=0) =
  if (n == 1) return a
  if (n % 2 == 0) return stop(n / 2, a + 1)
  return stop(3 * n + 1, a + 1)