What happens when we return with a Sum in C ?-CodePudding

int sum(int k) {
  if (k > 0) {
    return k   sum(k - 1);
  } else {
    return 0;
  }
}

int main() {
  int result = sum(10);
  cout << result;
  return 0;
}

It's a C code I don't understand, when you return in the 3rd like (return k sum(k-1); aren't we returning 10 9 together? Not like 10 9 8 7 6 5 4 3 2 1=55 (Original Output)

shouldn't this be the output? by this I mean like the return is something like 10 9 then again 9 8 again 8 7 So the output might be like 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 0 0? (ac to me the sum would be like this) The output would be one hundred?

I know I am wrong but please clear this for me.

CodePudding user response：

This summation function is using recursion (basically when a function contains a callback of itself inside).

When you call sum(10), the value you will get is 10 sum(9), not just 10 9. Then sum(9) == 9 sum(8) and so on until sum(10) == 10 9 8 7 6 5 4 3 2 1 sum(0) which will break the recursion and will just return a constant 0, and the function will finally return 55.

There won't be any repeating results as sum(k - 1) does not contain k in its sum.

CodePudding user response：

The Sum function is equal to f(n) = n f(n - 1) on math statements.

f(10) = 10 f(9) = 10 9 f(8) = ... = 10 9 8 ... f(1) = 10 9 8 ... 1 f(0)

And,

f(0) = 0

So,

f(10) = 10 9 8 ... 1 0

CodePudding user response：

You can see what actually happens by using a debugger. Or by adding console output to the code:

#include <iostream>

int sum(int k) {
  if (k > 0) {
    auto sk = sum(k-1);
    std::cout << "sum(" << k << ") return " << k << "   " << sk << "\n";
    return k   sk;
  } else {
    return 0;
  }
}

int main() {
  int result = sum(10);
  std::cout << result;
}

Output is:

sum(1) return 1   0
sum(2) return 2   1
sum(3) return 3   3
sum(4) return 4   6
sum(5) return 5   10
sum(6) return 6   15
sum(7) return 7   21
sum(8) return 8   28
sum(9) return 9   36
sum(10) return 10   45
55

sum(10) returns 10 sum(9). It does not return 10 9. And sum(9) returns 9 sum(8) ... and so on... and sum(1) returns 1 sum(0) which is 1.

sum(k-1) call the function just like sum(10) calls it in main. Recursion often causes confusion, but it is not much different from calling an ordinary function (that might call others functions, including itself).

CodePudding user response：

It works exactly like these non-recursive functions, because recursive functions work exactly like non-recursive functions.

int sum_0() {return 0;}
int sum_1() {return 1   sum_0();}
int sum_2() {return 2   sum_1();}
int sum_3() {return 3   sum_2();}
int sum_4() {return 4   sum_3();}
int sum_5() {return 5   sum_4();}
int sum_6() {return 6   sum_5();}
int sum_7() {return 7   sum_6();}
int sum_8() {return 8   sum_7();}
int sum_9() {return 9   sum_8();}
int sum_10() {return 10   sum_9();}

int main() { cout << sum_10(); }