Determine whether a recursive function converges

Question

Consider the following recursive factorial function:

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

The above function converges for all positive integers including zero. However it doesn't converge for negative integers.

Next, consider the following program:

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

The above function converges for all integers.

I wanted to know how would you statically determine whether or not a recursive function converges.

Answer 1

It's a good thing that you didn't specify a language and implied that you were thinking of unbounded integers, because it means I can point you to this prototype analyzer for a toy language available as a web app.

With unbounded integers, rici is right, this is the halting problem. However, most other problems solved by static analyzers are also equivalent to the halting problem. That does not prevent the static analyzers in question from being useful. They work around the undecidability by accepting to have false negatives, false positives, or both.

If you prefer to use a C-like syntax, you can also use Frama-C's value analysis to determine whether a simple C program terminates. This analyzer does not handle recursive functions, and it treats integer types as bounded (which they are). Bounded integer types makes the problem easier in theory (for some definitions of the input language, it becomes decidable) but it is still hard in practice.

Answer 2

You can't, in the general case. That question is precisely the halting problem.

Here's a simple example of a recursive function which probably terminates for all positive inputs, written in tail-recursive style (the assertion that it halts for all positive n is the 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)