求和数字递归C++

Question

我正在尝试制作一个对数组或数字列表求和的递归程序。使用 visual studio 2013，C++ 控制台应用程序。

我的第一个问题是：现在我知道我有多少个数字，我知道我的数组的大小。我如何以事先不知道数字的方式对其进行编程，比如在计算数字时仍有新数字加起来，使用最少 space？

我的第二个问题是：我怎样才能改进仍然递归工作的程序，并且它的时间和 space 使用是最佳的？

这是我的代码：

// summing a list of number.cpp
#include "stdafx.h"
#include "iostream"
int array[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int sum = 0, i = 0;
int sumarray(int i){
    if (i < 9){
        sum += array[i];
        i++;
        sumarray(i);
    }
    else
        return sum;
}
int main(){
    std::cout << "sum is ::: " << sumarray(i);
    getchar();
}

Answer 1

如果 i >= 9，您的函数执行 return sum;。
（很好）

你的函数return if i < 9在哪里???

if (i < 9){
    sum += array[i];
    i++;
    sumarray(i);  // I see no return statement here!!
}

基本上，如果您调用 sumarray(3)，没有 return 语句 被命中。

在你的程序中，有一个名为i的全局变量。该函数还有一个局部参数，也称为 i.

局部变量阴影全局变量，所以对全局没有明确的用途i.

我会这样做：

int array[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

// Pass in the current index, and the size of the array
int sumarray(int i, int sz)
{
    if (sz == 0)
    {
        return 0;
    }
    return array[i] + sumarray(i+1, sz-1);
}

int main(){
    std::cout << "sum is ::: " << sumarray(0, 10);
    // Start at the beginning (index 0)
    // Run for 10 elements.
    getchar();
}

第一个递归调用将是 sumarray(1,9);，然后是 sumarray(2,8);...当最终 sumarray(10,0) 被调用时，它将 return 0.

Answer 2

在 C++ 中，您拥有以非常简单、可读且安全的方式执行此操作的所有工具。查看 valarray 容器：

#include <iostream>
#include <valarray>

int main () {
  std::valarray<int> array{1,2,3,4,5,6,7,8,9,10};
  std::cout << array.sum() << '\n';
  return 0;
}

Answer 3

对数组元素求和的函数通常接受数组作为参数。在那种情况下，实际上它还必须接受数组的大小。像这样：

int sumarray(int a[], size_t size) {

这样的签名还可以让您访问更好的递归方法。特别是，您可以递归计算数组前半部分和后半部分的总和，以及 return 它们的总和：

        size_t midpoint = size / 2;
        return sumarray(a, midpoint) + summaray(a + midpoint, size - midpoint);

这不是一个完整的解决方案：您需要一个终止条件（当 size 小于 2 时）。将其放入并完成函数留给您作为练习，因为如果您必须自己投入一些工作，您会学得更好。

该方法将递归深度和堆栈大小（内存开销）限制为与数组大小的对数成正比，尽管它仍然涉及与数组大小成比例的函数调用总数和整数加法。我认为您无法使用递归算法实现更好的渐近 space 或时间复杂度。（但是，此任务的非递归算法只需要固定数量的函数调用和固定数量的内存开销。）

Answer 4

我希望您停止编写依赖于全局变量的函数，因为它们可以很容易地只根据提供的输入工作。

这是适合我的版本。

#include <iostream>

int sumarray(int array[], int i)
{
   if ( i <= 0 )
   {
      return 0;
   }

   return sumarray(array, i-1) + array[i-1];
}

int main()
{
   int array[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   std::cout << "sum is : " << sumarray(array, 0) << std::endl;
   std::cout << "sum is : " << sumarray(array, 5) << std::endl;
   std::cout << "sum is : " << sumarray(array, 10) << std::endl;
}

输出：

sum is : 0
sum is : 15
sum is : 55

Answer 5

这是我在 Qt 中编写的有效 C++ 代码 - 祝你好运我添加了一些调试点输出以使其理解更清楚

#include <QCoreApplication>
#include <QDebug>
int sum=0;
int sumrec(int *array,int n)
{

    if (n>=0)
    {
       int element=*(array+n); // note *(array+n) -> moving the pointer
                               //      *array+n   -> this is adding n to the pointer data (wrong)
                               // what is array ?
       qDebug() << " element value " << *(array+n) << " at n=" << n << " array address = " << array;
       n--;
       sum=sum+element;
       qDebug() << "sum = " << sum;
       sumrec(array,n);
       return sum;
   }
   else
   {
       return 0;
   }

}


int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    int A[10]={12,13,14,15,16,17,18,19,20,11};
    int b=sumrec(&A[0],9);

    qDebug() << "answer = " << b;

    //return a.exec();
}

这是终端的输出

element value  11  at n= 9  array address =  0x7fff5fbffb78 
sum =  11 
 element value  20  at n= 8  array address =  0x7fff5fbffb78 
sum =  31 
 element value  19  at n= 7  array address =  0x7fff5fbffb78 
sum =  50 
 element value  18  at n= 6  array address =  0x7fff5fbffb78 
sum =  68 
 element value  17  at n= 5  array address =  0x7fff5fbffb78 
sum =  85 
 element value  16  at n= 4  array address =  0x7fff5fbffb78 
sum =  101 
 element value  15  at n= 3  array address =  0x7fff5fbffb78 
sum =  116 
 element value  14  at n= 2  array address =  0x7fff5fbffb78 
sum =  130 
 element value  13  at n= 1  array address =  0x7fff5fbffb78 
sum =  143 
 element value  12  at n= 0  array address =  0x7fff5fbffb78 
sum =  155 
answer =  155

求和数字递归C++

summing numbers recursive C++

c++

arrays

recursion