Can't understand recursion output

Question

I don't understand the following recursive code.

  int func(int num){
  if(num == 1){

   return 1;   
    }
    else{

    return (func(num-1) + num));
   }
 }
public static void main(String[] args) {

System.out.println(func(100));

 }

So the output is 5050. I don't understand why that is. Can someone explain to me the working of the code?

Hi, welcome here. Don't worry, your misunderstanding probably comes from the lack of practice. Take a piece of paper. Pass a smaller number, let's say 5. Write down what comes in and what comes out. Do it for each number - 4, 3, 2, 1. When you've got 1, you will be able to return a concrete value and resolve the returns you've written above - (1), (1 + 2), (3 + 3) — Andrew Tobilko, May 02 '19 at 20:43
@AndrewTobilko Wouldn't it be far better to mark it as duplicate of a question that is not itself closed? — Sylwester, May 02 '19 at 20:58
@Sylwester it was suggested and it's pretty popular. You may suggest other related questions, I will include them. — Andrew Tobilko, May 02 '19 at 21:12

score 0 · Answer 1 · edited May 02 '19 at 20:39

Ok, so let's analyze from the beginning the behaviour of your code step by step:

First of all, you call func(100)

100 is different than 1 so the first 'if' is skipped, the function "func(100)" returns 100 + func(99)
99 is different than 1 so the first 'if' is skipped, the function "func(99)" returns 99 + func(98)

so for the moment "func(100)" returns 100 + 99 + func(98)
same steps as before for func(97) until func(2)

so your function "func(100)" returns 100 + 99 + 98 + 97 + ..... + 2 + func(1)
func(1) 'if' this time is not ignored so func(1) returns 1
now you have func(100) = 100 + 99 + 98 + ..... + 2 + 1 which is the sum of the first 100 positive integers which is 5050

score 0 · Answer 2 · answered May 02 '19 at 20:35

Let's do it again with 3. Add system.out at every line.

The thing is when a function call happen, current function execution stops until the new function end and gives its result. This is the program stack: the list of functions that wait for a subfunction to terminate.

With the code you provide, you will have a stack of 100 "func" calls, then the last call contain num == 1, because you have decremented 99 times 100.

After that all of the 100 func will return, each with the + num addition.

Can't understand recursion output

2 Answers2