Given a non-negative number n find its factorial without using Recursion.
n! = 1 * 2 * 3 * 4 * ...... n-2 * n-1 * n
Also, implement using a recursive method. Factorial can be recursively expressed as
factorial(n) = n * factorial(n - 1)
This is definitely a very trivial exercise. But the exercise is deliberately kept trivial so that one can concentrate on other important aspects of the art of coding which are listed below.
The final point is a really interesting one. In real life projects sometimes it becomes necessary to convert a recursive method into an iterative method if the nesting of recursive calls could become too deep and could result in a Stack Overflow. Hence in such cases, a recursive implementation has to be converted into an iterative one.
Here are a couple of interview questions I ask about Recursion. For the second question, I usually do not get a complete answer. 😉
When a method or function is called a Recursive Method?
A method or function that calls itself is called a recursive method or recursive function. A recursive method MUST have a Terminating Condition, otherwise, it would result in an infinite recursion. In trivial problems like this Factorial exercise, the Terminating Condition is obvious and hence could be easily spotted. But when the logic is complex there could be corner cases where the Terminating Condition may get missed and result in infinite recursion causing the Stack Overflow. Since the error does not happen all the time it makes it difficult to spot and fix it. Such errors always have a knack of showing up during a demo or at the customer site. That's why while using recursion, one should have a keen eye to ensure the execution of Terminating Condition under all circumstances.
What are the overheads of a Recursive Method?
Many of the overheads are related to the Stack Memory.
Trivia - What is Tail Recursion and why as a programmer one needs to be aware of it?
I shall answer this Trivia when I post the link to my solution.
This is the first exercise where we shall have both recursive and iterative implementation. Going forward we shall see several more exercises where we shall have both the implementations. In this case, converting a recursive implementation into an iterative one may be trivial. But in some cases, it could be tricky and non-trivial.
I strongly urge the readers to make a sincere attempt in implementing the solution. I am providing my implementation so that you can compare it with yours. Looking straightaway at my solution may not be as helpful as making a physical attempt to solve the problem even if your solution is incomplete or not perfect.
You could also carry your source code in a public repository hosted on GitHub and if you prefer you could share the link to your source code in the comment section so that other readers could take a look at it and provide their comments.
Please provide your support and express your encouragement by using the social buttons provided below and share this effort with others.
Here is the link to my solution.
Tail Recursion
Let me borrow a code snippet from the solution to "Towers of Hanoi", courtesy GeeksforGeeks.
Please notice that the very last statement is a recursive call and its return value is not used and in this case, the function is declared void and does not return anything. This is called Tail Recursion and why it is important is because very easily the tail-recursive call could be completely avoided.
Let us make the changes and eliminate the tail-recursive call.
n! = 1 * 2 * 3 * 4 * ...... n-2 * n-1 * n
Also, implement using a recursive method. Factorial can be recursively expressed as
factorial(n) = n * factorial(n - 1)
This is definitely a very trivial exercise. But the exercise is deliberately kept trivial so that one can concentrate on other important aspects of the art of coding which are listed below.
- Check for illegal arguments and handle them.
- Inline comments.
- JavaDoc for the class.
- JavaDoc for all the public methods.
- Ability to convert a recursive method into a non-recursive method.
The final point is a really interesting one. In real life projects sometimes it becomes necessary to convert a recursive method into an iterative method if the nesting of recursive calls could become too deep and could result in a Stack Overflow. Hence in such cases, a recursive implementation has to be converted into an iterative one.
Here are a couple of interview questions I ask about Recursion. For the second question, I usually do not get a complete answer. 😉
When a method or function is called a Recursive Method?
A method or function that calls itself is called a recursive method or recursive function. A recursive method MUST have a Terminating Condition, otherwise, it would result in an infinite recursion. In trivial problems like this Factorial exercise, the Terminating Condition is obvious and hence could be easily spotted. But when the logic is complex there could be corner cases where the Terminating Condition may get missed and result in infinite recursion causing the Stack Overflow. Since the error does not happen all the time it makes it difficult to spot and fix it. Such errors always have a knack of showing up during a demo or at the customer site. That's why while using recursion, one should have a keen eye to ensure the execution of Terminating Condition under all circumstances.
What are the overheads of a Recursive Method?
Many of the overheads are related to the Stack Memory.
- Function Return Address - The return address of the calling method (caller) gets added to the Call Stack.
- Function Parameters - The arguments of the function are placed on the stack by the calling method.
- Automatic Variables or Local Variables - The local variables of the called method make use of the stack memory.
- Function Return Value - Unless the function return value is declared void, the return value is placed on the stack when the function returns.
- Function Call Overhead - Though this is not related to stack usage, it is the delay caused due to the preparation that needs to be made before making a function call and the cleanup that should be done after the function returns (popping of stack frame).
Trivia - What is Tail Recursion and why as a programmer one needs to be aware of it?
I shall answer this Trivia when I post the link to my solution.
This is the first exercise where we shall have both recursive and iterative implementation. Going forward we shall see several more exercises where we shall have both the implementations. In this case, converting a recursive implementation into an iterative one may be trivial. But in some cases, it could be tricky and non-trivial.
Factorial Implement the class Factorial with the following public methods public int factorialUsingRecursion(int n); public int factorial(int n);
I strongly urge the readers to make a sincere attempt in implementing the solution. I am providing my implementation so that you can compare it with yours. Looking straightaway at my solution may not be as helpful as making a physical attempt to solve the problem even if your solution is incomplete or not perfect.
You could also carry your source code in a public repository hosted on GitHub and if you prefer you could share the link to your source code in the comment section so that other readers could take a look at it and provide their comments.
Please provide your support and express your encouragement by using the social buttons provided below and share this effort with others.
Here is the link to my solution.
Tail Recursion
Let me borrow a code snippet from the solution to "Towers of Hanoi", courtesy GeeksforGeeks.
// Java recursive function to solve tower of hanoi puzzle
static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
{
if (n == 1)
{
System.out.println("Move disk 1 from rod " + from_rod + " to rod " + to_rod);
return;
}
towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
System.out.println("Move disk " + n + " from rod " + from_rod + " to rod " + to_rod);
towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}
Please notice that the very last statement is a recursive call and its return value is not used and in this case, the function is declared void and does not return anything. This is called Tail Recursion and why it is important is because very easily the tail-recursive call could be completely avoided.
Let us make the changes and eliminate the tail-recursive call.
// Java recursive function to solve tower of hanoi puzzle
static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
{
// Introducing while loop
while (true)
{
if (n == 1)
{
System.out.println("Move disk 1 from rod " + from_rod + " to rod " + to_rod);
return;
}
towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
System.out.println("Move disk " + n + " from rod " + from_rod + " to rod " + to_rod);
// Eliminate Tail Recursion
if (n > 1)
{
char temp_rod;
temp_rod = from_rod;
from_rod = aux_rod;
aux_rod = temp_rod;
n--;
}
}
}
You can see that in the above code, with few extra lines code we avoided the recursive call just because it happened to be the last statement in the method and its return value was not used. Sometimes in production, there may be a requirement to avoid Stack Overflow situation due to certain input or to speed up the running time of the method by avoiding the recursive call. In such situations, if the programmer spots that the call is tail-recursive then very easily the code could be optimized and the recursive call could be eliminated. If the concept of Tail Recursion is not known how could any optimization be possible?
In the above code, we unnecessarily introduced a redundant if block. We could as well use an Anonymous Block as shown below. If an optimizing compiler is capable of eliminating tail recursion then these are the exact changes that would be done by the compiler automatically.
// Java recursive function to solve tower of hanoi puzzle
static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
{
// Introducing while loop
while (true)
{
if (n == 1)
{
System.out.println("Move disk 1 from rod " + from_rod + " to rod " + to_rod);
return;
}
towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
System.out.println("Move disk " + n + " from rod " + from_rod + " to rod " + to_rod);
// Eliminate Tail Recursion using Anonymous Block
{
char temp_rod;
temp_rod = from_rod;
from_rod = aux_rod;
aux_rod = temp_rod;
n--;
}
}
}
The Trivia about Tail Recursion is to emphasize a point that any topic we know, we should know it clearly and completely. The moment we understand Recursion then there is a tendency to feel that we understand it fully and do not make any further effort. The idea is to recognize and beware of the "taking for granted" approach. So any topic, for that matter as simple one like Recursion, we should search and read 10-15 different articles and try to learn and know everything about it. We may not know all the topics and may not be practically possible also but it is definitely possible to know what we know very thoroughly, clearly and completely.
We also need to develop a voracious appetite about various things related to our field of profession.
In early 2000, a company approached me for software consultation as one of their software projects was lagging behind by one and a half year and the customer was breathing down their neck. The project was written in C language and they had successfully delivered it for Windows but have been unable to deliver it for Sun Spark Station running Sun OS. The team consisted of around six people and the Technical Lead had a Masters degree in Computer Science.
When I went in and got involved I quickly came to know that nobody in the team had even remotely heard about Endianness - the Big-Endian and Little-Endian. In fact, that was the only concept the team had to know to deliver the project. They were looking everywhere and doing all kinds of experiments and tinkering except knowing about Endian. It was like somebody losing a golden ring in one place and searching in a different place just because the place where the ring was lost was dark and hence searching was done in a different place because it was well lit. 😀
I absolutely had no complaints, got paid handsomely for 3 months for my consultancy and helped the team deliver successfully after fixing 300 and odd bugs. I was glad that though facility like Wikipedia was not available during the 1990s I happened to know about the Endian concept even though I never had a chance to make use of it until that particular opportunity.
Knowing stuff does help. Nobody can deny that "Knowledge is Power".
Post a Comment
Post a Comment