使用递归检查数组元素是否是两个较早元素的总和

Question

当我偶然发现这个问题时，我正在解决一本书上的练习题：

*描述一个递归算法，该算法将检查整数数组 A 是否包含整数 A[i]，该整数是 A 中较早出现的两个整数的总和，即，使得

 A[i] = A[j] +A[k] for j,k < i.

*

我已经考虑了几个小时，但一直无法想出一个好的递归算法。

Answer 1

没有任何循环的递归解决方案（伪代码）：

bool check (A, i, j, k)
    if (A[j] + A[k] == A[i])
        return true
    else
        if      (k + 1 < j)      return check (A, i, j, k + 1)
        else if (j + 1 < i)      return check (A, i, j + 1, 0)
        else if (i + 1 < A.size) return check (A, i + 1, 1, 0)
        else                     return false

递归函数用 调用check(A, 2, 1, 0)。为了突出显示该算法的主要部分，它不会检查数组最初是否具有两个以上元素。