递归-n个自然数之和

Question

计算n个自然数之和的函数

int solve(int n)
{
    if(n==0 or n==1)
    return n;
    int sum=0;

    sum=sum+n;
    solve(n-1);   // gives me wrong output

    return sum;
}

int solve(int n)
{
    if(n==0 or n==1)
    return n;
    int sum=0;

    sum=sum+solve(n-1);  // gives me correct output

    return sum;
}

函数的工作或输出有何不同，因为调用堆栈在两种情况下的工作方式相同

Answer 1

这两个函数有很多共同点。

因为参数类型是int，所以可以用负参数调用函数。在这种情况下，您会得到毫无意义的结果。

累加数字总和的变量类型应大于 int 类型以避免溢出。

第一个函数总是return在函数的第一次递归调用中传递的参数值。

此声明

solve(n-1);   // gives me wrong output

没有效果，因为未使用 returned 值。

由于此语句

，第二个函数总是 returns 0 或 1（前提是传递了 non-negative 参数）

if(n==0 or n==1)
return n;

因为在这段代码中

int sum=0;

sum=sum+solve(n-1);  // gives me correct output

未使用参数的当前值。

好像有错字，应该这样写

sum = n + solve(n-1);  // gives me correct output

函数可以按照下面的演示程序所示的方式声明和定义。

#include <iostream>

unsigned long long sum( unsigned int n )
{
    return n == 0 ? 0 : n + sum( n - 1 );
}

int main()
{
    std::cout << sum( 100 ) << '\n';
    
    return 0;
}

程序输出为

函数中的return语句也可以这样写

return n < 2 ? n : n + sum( n - 1 );

为了减少递归调用的次数，可以按以下方式重写函数

#include <iostream>

unsigned long long sum( unsigned int n )
{
    return n < 2 ? n : sum( n - 2 ) + n + n - 1;
}

int main()
{
    std::cout << sum( 100 ) << '\n';
    
    return 0;
}

Answer 2

solve 第一种方法中的函数在你的程序中没有任何作用

int solve(int n)
{
    if(n==0 or n==1)
    return n;
    int sum=0;

    sum=sum+n;
    solve(n-1);   // has not any effect

    return sum;
}

在第二种方法中，returned 值将始终为 1，而它必须 return 数字的总和，计算数字总和的正确代码是：

int solve(int n)
{
    if (n == 0 || n == 1)
        return n;

    int sum = 0;

    sum = n + solve(n - 1);  // change 'sum' with 'n'

    return sum;
}

运行:

solve(5);

输出：

5 + 4 + 3 + 2 + 1 = 15

递归-n个自然数之和

Recursion- sum of n natural number

c++

recursion

callstack

function-definition