一个递归函数,用于查找c中数组的总和

Question

我必须找到一个递归函数,通过反复将它分成2个几乎相等的部分来找到数组的总和？

我的方法应该是什么？我该怎么办？

我不要求代码!只是提示或方向来解决这个问题!

Answer 1

这很容易.数据集上的每个递归算法都应该根据相同的算法^(a)在更简单的数据集上定义,并且具有终止条件.

在这种情况下,终止条件是大小为1的数据集,您只需返回该值,否则每个递归级别只是在两半上执行相同的任务,然后将两个结果一起添加.

这将类似于以下伪代码:

def sumof (array, start, end):
    if start == end:
        return array[start]
    midpoint = (start + end) / 2
    return sumof (array, start,        midpoint) +
           sumof (array, midpoint + 1, end     )

现在,您所要做的就是将其转换为您选择的语言并调试边缘情况下的任何潜在问题.

让我们看看零索引的七元素数组中的数字10到16是如何工作的.如果你通过你的头脑或者纸上运行该算法,如果你还没有成为比我更多的机器:-),你会得到这样的东西:

Level 0, call sumof (array, 0, 6):
    Level 1, call sumof (array, 0, 3)
    +---Level 2, call sumof (array, 0, 1)
    |   +---Level 3, call sumof (array, 0, 0), returns 10
    |   |---Level 3, call sumof (array, 1, 1), returns 11
    |   Add together to get 21
    |   Level 2, call sumof (array, 2, 3)
    |   +---Level 3, call sumof (array, 2, 2), returns 12
    |   |---Level 3, call sumof (array, 3, 3), returns 13
    |---Add together to get 25
+---Add together to get 46
|   Level 1, call sumof (array, 4, 6)
|       Level 2, call sumof (array, 4, 5)
|       +---Level 3, call sumof (array, 4, 4), returns 14
|       |---Level 3, call sumof (array, 5, 5), returns 15
|   +---Add together to get 29
|   |---Level 2, call sumof (array, 6, 6), returns 16
|---Add together to get 45
|
Add together to get 91

^(a)情况并非总是如此,有时候实际算法也会发生变化,但很少见到这一点.