1
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.

Nilesh
  • 23
  • 3
  • 4
    You could try stepping through the code with a debugger and see for yourself. – Quimby Mar 22 '22 at 11:40
  • You could instead try `int result = sum(3);` and debug by stepping through the code line by line looking at the 1 variable and the flow after each step. – drescherjm Mar 22 '22 at 12:27
  • Except as an exercise, you should never use recursion for O(n) algorithm, just use a loop (safer, faster, less code). – prapin Mar 22 '22 at 13:16
  • @Quimby Yeah, I know but I was new that time, and I am still learning how to use a debugger, although I know how to use one, but to set it up with VSCode is a headache for me at least for now. – Nilesh Apr 22 '22 at 11:12

4 Answers4

7

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.

6

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

BBing
  • 152
  • 5
5

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).

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
4

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(); }
molbdnilo
  • 64,751
  • 3
  • 43
  • 82