I would say yes...
Non-recursive algorithms are executed only once to solve the problem and Recursive algorithms self invokes itself repeatedly until a certain condition is met regarding the algorithm.
When a function is called a stack frame is created for that. Creating a stack frame takes lot of resource allocation in memory. Activation of a function takes a stack frame pushed in to stack. So until a specific condition for the function meet stack frames are pushed to stack. After the condition has been met they will be popped out from the stack. Stack frames are space consuming and pushing and popping of stack frames is an overhead.
Almost all recursive algorithms can be written as non-recursive algorithms. Following is an example of non recursive algorithm for counting factorial.
public static long factorial (int n) {
long result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
Most of the recursion can be eliminated by using looping. In some programming languages they convert intermediate code to machine code when they execute such loop. So it is very efficient to use such non recursive algorithm. This is more efficient than executing byte code.
In languages like C++, C we can declare the loop counting variable using keyword “register”, so that the looping is efficiently done.
Considering these facts I can say a non-recursive algorithm can be more efficient in most computers than a recursive algorithm of same theoretical complexity.
1 comment:
Machan there is one other thing regarding recursive algorithms. They can easily produce bugs. Consider the following code
// include stdio.h header here
int num1,num2; // global variables
int main()
{
printf("%d\n" ,fibonacci(1));
printf("%d\n" ,fibonacci(2));
printf("%d\n" ,fibonacci(3));
printf("%d\n" ,fibonacci(4));
printf("%d\n" ,fibonacci(5));
printf("%d\n" ,fibonacci(6));
printf("%d\n" ,fibonacci(7));
printf("%d\n" ,fibonacci(8));
}
int fibonacci(int n)
{
if(n == 0)
return 1;
else if(n == 1)
return 1;
else{
num1 = fibonacci(n-1);
num2 = fibonacci(n-2);
return num1 + num2;
}
}
Compile and see the out put.You'll see that the out put is not what it should be. This happened because variables num1 and num2 are defined as global variables. This is the bug in the program. Since they are global the copy of that variable will not save in the stack frame of each function call. But the global variables will be updated giving incorrect outputs.
Post a Comment