Recursion of C# Code - Trouble understanding

Question

For one of the coding projects in C# methods, it wanted me to create a function that would take the level of the game, and add the points for each level before to the points of the last level. Example: level 3 = 3 points. add 3 + 2 + 1.

I was expecting a Forloop since the code seemed to be iterated through each level but instead the following worked:

static int Points(int levels)
{
//your code goes here
if (levels == 1)
{
return 1;
}
return levels + Points(levels - 1);
}

I'm having trouble understanding how this snippet of code is able to go through each of the previous levels. From just reading it, it seems like it would on return level + Points(level - 1) just one time. Can anyone explain this to me? I'm not sure if i missed something.

Thanks!

Answer 1

The key is in Points(levels-1). Suppose you code works correctly, then Points(levels-1) is the sum of all points up to levels-1. Then all you need is to add the current level. That is, the answer is: levels + Points(levels-1).

Recursion is inherently a declarative programming style while C# mostly works in an imperative fashion (especially at the novice level). That is probably why you (and many others besides you) struggle with it at first. Not to worry, after a while it will sink in.

Some may suggest to unroll the recursion(e.g. Points(5) will call 5+Points(5-1) which calls 5+4+Points(3) and so on until you reach the base case where the recursion stops). This may help at the beginning, but jn my opinion is the wrong way to reason about recursion. Recursion can get complex, and then manually unrolling will fail you!

Answer 2

Ani Jona 🕊 thanks for the info! From what I'm understanding, you're pretty much saying to just understand the format calls a recursion In the same way console.writeline may call printing to the console? Maybe a bad example but basically just know that specific syntax?

Answer 3

Yes. It is not quite that simple though. It depends much on the base case if the recursion works correctly or not. But essentially when reading a recursive algorithm, at a first glance, I would say yes, assume that the function does exactly what it is supposed to do. Hopefully it has a descriptive name. With those partjal results, look what the function makes of it and eventually returns.

Writing a recursive algorithm is a little different. At first you need to realise that a solution to a problem can be expressed as solution to a problem of a smaller size. If it is then write the recursive function so that it expresses the solution in terms of a solution of a smaller size. Add the base cases and you should be home free.

Answer 4

It's simple, just trace it:

Points(3) = 3+Points(2) = 3+2+Points(1) = 3+2+1 = 6