How cool is that?Now we implemented a tail recursion properly, but how can I check if my new random function was implemented correctly?Well, the simplest test ever is just execute your function with a very large input, another simple test is check the call stack.
But of course, there’s a more accurate test.
IL DisassemblerYou can use the IL Disassembler in order to make a more deep analysis.
If you don’t know IL at all, I strongly recomend you to check this link.
Here’s a quick overview: IL is the intermediate language generated by .
NET compiler.
When you compile your .
NET code this is the result, which’ll be compiled again in execution time (JIT).
The IL Disassembler can be open by Visual Studio Developer Command Prompt, you can type “developer command” at Windows search box and it’ll be listed (it looks like the regular command prompt).
You can navigate to your project folder and execute the command ildasm project-name.
dll , it’ll open the IL Disassembler, as shown in the following image:Now, let’s check the first sum function, which raised the StackOverflow exception.
Maybe the IL language looks weird to you, but this isn’t a problem, we don’t want to understanding the language in a comprehensive way right now.
Let’s focus on call instruction, it happens in four different moments:IL 003 — call to get_TailOrNull() function;IL 011 — call to get_TailOrNull() function;IL 018 — call to get_HeadOrDefault() function;IL 020 — call to sum function;The last call is the most important one, because it shows that a new call really occurs here.
Now, let’s check the tailRecursionSum function:Oops, something is wrong, there’s also a call instruction here.
Well, actually to check our recursive function we need to open the nested function.
In order to open this IL code, we need to navigate at program tree and open the Invoke file:Now, let’s see the code:There’s also three call instructions here.
But if we look carefully we gonna see that all calls are related to head and tail functions.
Instead our last recursive call we can see a br.
s instruction, which works like a JUMP to another instruction.
In this specific case, a JUMP to the first instruction (IL_0000 ).
Just before this br.
s we can see two starg.
s instructions, this is a short for store argument, in other words, our IL code is updating the value of the arguments (acc and list), and after that, it’ll back to the first instruction with updated values, like an regular loop.
Because of this JUMP structure, there’s no Stackoverflow and there’s a performance improvement, it’s really nice to see how the things works under the hood.
.