c++ - 我如何递归地重写这个？

Question

我迭代写了一堆函数代码，我只想递归重做。我怎么做？没有不变量，我有点迷路。

当给定两个整数 low 和 high 时，该过程 计算函数 f 的过程将计算 f(low) + f(low + 1) + f(low + 2)+....+ f(高)。例如，( sumFunc(1, 9, square) == 285 )

int sumFunc(int low, int high, int f(int), int end) {
    if ( low == high)
        return f(low) + end;
    else 
        return sumFunc((low + 1), high, f(end + (f(low))));
}

int sum(int low, int high, int f(int)) {
    return sumFunc(low, high, f(int), 0);
}

谢谢!

Answer 1

我认为这就是您所追求的。这是不太安全的版本，要求调用者确保 low 在调用时不大于 high:

int sum(int low, int high, int f(int))
{
    return f(low) + ((low == high) ? 0 : sum(low+1, high, f));
}

如果在调用时 low 永远大于 high 是完全可能的，这需要一些安全检查以确保你不调用溢出。

int sum(int low, int high, int f(int))
{
    if (low < high)
        return f(low) + sum(low+1, high, f);

    if (high < low)
        return f(high) + sum(high+1, low, f);

    return f(low);
}