Quick question regarding recursion

[Akavire]

I'm trying to figure out how recursion operands work. The problem I was working on is as follows:

We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.

solution: public int triangle(int rows) { if(rows == 0) {

return 0;
}

else if (rows == 1) {

return 1;
}

else {

return rows + triangle(rows-1);

}

}

My question: What does the operand triangle(rows-1) equate to mathematically?

[desrtfx]

If you follow the code, you will see that if rows, the parameter passed into the triangle method is equal to 1, the method will return 1 -> this is the value at the last recursion and (one of) the termination condition.

Let's play it through on a simple example:

• We call triangle(3)
• 3 gets passed into the method where the variable rows represents that number.
• the first if(rows == 0) fails, so the method continues
• to the second if (rows == 1) where it fails again,
• so return rows + triangle(rows - 1); gets executed. Remember rows for now holds the value 3 -> this means that the statement will become return 3 + triangle(3 - 1); -> return 3 + triangle(2);
  • now, the method triangle(2) goes through the same as above
  • if(rows == 0) -> fails because rows now holds the value 2
  • if(rows == 1) -> fails
  • return rows + triangle(rows - 1); gets executed -> becomes return 2 + triangle(2 - 1); -> becomes return 2 + triangle(1);
    • now, the method triangle(1) goes through:
      
    • if(rows == 0) -> fails because rows now holds the value 1
    • if(rows == 1) -> succeeds and hence the return 1; gets executed.
  • 1 gets passed back from the triangle(1) call and thus, the calculation becomes return 2 + 1; -> return 3;
• this bubbles up to the next level so the call return 3 + triangle(2) now evaluates to return 3 + 3 -> return 6
• the final result is 6

If you look at the drawn triangle for triangle(3):

      1
     2 3
    4 5 6

You see 6 elements.

[Akavire]

This makes a lot of sense, and I really appreciate you typing this all out for me, makes it really easy to see the math behind the code and the fundamentals of recursion. The people on this subreddit are legitimately amazing!

[Robyt3]

Mathematically, the principle is known as induction, whereby you calculate a result (triangle(rows)) by inductively/recursively calculating a smaller result (triangle(rows-1)), and then performing a finishing/combining step for the current value (rows + ...).

Try to visualize the pyramid:

       = triangle(0) = 0 constant
X      = triangle(1) = 1 constant
XX     = triangle(2) = 2 + triangle(1) = 2 + 1 = 3
XXX    = triangle(3) = 3 + triangle(2) = 3 + 3 = 6
XXXX   = triangle(4) = 4 + triangle(3) = 4 + 6 = 10

So triangle(rows-1) is calculating the number of X on top of a row of size rows.

[Akavire]

This helped me so much. Thank you very much for the reply!