Hello, everyone, today we’ll talk a little more about recursion.
I came here to explain the question I left on the last post.
What can be done about that recursive method? How can we “fix” it? There’s a way to implement recursion that is called tail recursion.
This process is different, it is as performatic as an iterative process, but it usually requires an auxiliary method to be implemented.
We can identify tail recursive functions if we analyse how they are executed, let’s try it out, shall we?
we’ll evaluate the calculation of the factorial of the number 5, according to the following algorithm:
def factorial(num: Int):Int = {
if(num == 0) 1 else num * factorial(num - 1)
}
Execution:
We can see that when the method returns it’s final value, there is still some computation to be done, and the expression grows in length at every recursion, this indicates that it is not implemented with tail recursion.
Now let’s analyse the new tail recursive algorithm, and evaluate it’s execution as well.
def factorial(num: Int):Int = {
def factorialIter(num: Int, acc: Int):Int = {
if(num == 0) acc else factorialIter(num - 1, acc * num)
}
factorialIter(num, 1)
}
Now let’s see the difference in the execution:
We can see that in every step, the length of the expression is the same, this indicates that this is tail recursive. In fact, the name itself tells us how to identify a tail recursive function, we call it that because the recursive call is at the very last statement of the algorithm, or the tail, indicating that when the function returns it’s value, nothing more will be computated, avoiding the problem that existed on the previous algorithm.
The examples were written in Scala, because it’s compiler (scalac) optimizes tail recursive functions, so the call stack won’t grow, on the other hand, the Java compiler (javac) doesn’t, so the stack grows normally, throwing StackOverflowError the same as before.
Just out of curiosity, in Scala there is an annotation that “forces” a function to be tail recursive, if this annotation is present, the class won’t even compile if the method isn’t implemented with tail recursion, this helps the developer to make sure that he’s doing what he wants to do 
Here’s an example of our function rewritten with the @tailrec annotation
def factorial(num: Int): BigDecimal = {
@tailrec def factorialIter(num: Int, acc: BigDecimal): BigDecimal = {
if (num == 0) acc else factorialIter(num - 1, acc * num)
}
factorialIter(num, 1)
}
Hint: If you want to test this code, you should alter the implementation return BigInteger or BigDecimal (like I did on the last example), because Int won’t allow you to test with large numbers.
I hope you enjoyed it, see you next time
Good read!
WOOOOOW
nice example. thanks for sharing.
Thank you for your comment!
I’m happy to help!
maybe I’m just confused by terminology here. the factorial function defined with the accumulator is what I have been taught to call “memo-ization”. is this distinct in any way from tail recursion? based on what is explained in the article here it looks like the terms are synonyms. can somebody provide an example of a memo-ized recursive algorithm that is NOT tail recursive?
Memoization is a technique in which the results of calling a function on a particular set of arguments are stored in a data structure (usually a hash table) indexed by those arguments before returning, so that subsequent calls to that function with the same arguments can simply return the result stored in the table rather than performing potentially expensive calculations instead. It’s mostly useful in situations where you would expect to be calling the same function with the same arguments many times, especially during recursion.
I didn’t know about that technique, thanks to both of you for leaving this, it surely enriches the post
Excellent share. Very interesting.
I’m glad I can help
Thank you for the support.
its its its its its its its its its its its its its its its its its its its its its its its its its its thank you
Nice.
But you missed the final method call before 120 is returned.
…
factorialIter(0, 120)
120
Or did I misunderstand something?
My bad
You got it perfectly, I just made a mistake there ^^
I fixed it, thanks for bringing it to my attention
def path_count(x, y):
return 1 if x <= 0 or y <= 0 else path_count(x-1, y) + path_count(x, y-1)
def path_count(x, y):
def c_iter(x, y, acc):
return acc if x <= 0 or y <= 0 else c_iter(x - 1, y, acc + path_count(x, y -1))
return c_iter(x, y, 1)