• Create Account

#ActualblueEbola

Posted 03 February 2012 - 03:33 AM

I am curious I was asked a question today that just irks me cause I didn't know the answer and I blanked out. Here is a sample code that I wrote to show you. There are tons of examples on it anyways I just can't seem to find the answer.

function factorial($factor) {$temp;
if ($factor <= 1) return 1; return$temp = $factor * factorial($factor - 1);
}
// Example use

echo factorial(3);


Doesn't really matter what language as long as it allows you to call the function in its function.

Anyways the question was what is the advantage and disadvantage of using this... I froze so bad! Anyone able to explain this to me there was no over the other. I can write it in a different language if you don't understand it, but I am sure that won't be the issue. Thanks in advance.

There are times when recursion makes a lot of sense and can give you an elegant algorithm. Namely when the problem at hand is nothing more than a series of extremely similar sub-problems. Printing out a binary tree in sorted order looks way better in recursive form than the equivalent iterative solution (Python code):

NOTE: don't hate if there are minor issues with either of these functions, I haven't tested them!

The recursive solution is far easier to understand (imo) than the iterative solution. The recursive solution implicitly takes care of the stack state for us, while the iterative solution has to implement it's own stack in order to operate in the same way. That makes the recursive solution much more elegant, but it's not without it's drawbacks. As Washu mentioned, compilers tend to optimize out recursive functions with "tail call optimization" -- which means that if the recursive call to the same function is the last expression in the function, the compiler can turn it into an iterative form behind the scenes and do away with a stack overflow from occurring for monstrous recursive call chains. In the above implementation we have two recursive calls and that is problematic: if the tree is big enough, our "print_binary_tree(tree.left)" call will dig deep into the tree will take up a lot of memory on the stack before it hits an exit condition.

Some languages impose a hard limit on the amount of non-tail optimized recursive calls you can do: I believe Python will stop you after your stack depth gets a couple thousand calls deep. Other languages that are less safe like C++ will let you go on until you receive a stack overflow exception. Some compiled languages will even give you a warning when they detect that a recursive method is not optimized for tail call recursion.

At that point you have a few choices: you can rewrite your recursive function to utilize tail call optimization by making the only recursive call the last expression in the function, or you can just scrap it and rewrite it iteratively. The iterative solution can maintain it's stack in a memory space (such as the heap) that can grow much larger as needed. Rewriting the above recursive print_binary_tree function to utilize tail call optimization would look like this:

It does basically what the iterative solution does, except without the while loop. I think it's a bit prettier than the iterative solution, but the difference is negligible.

What you choose to do will depend entirely on the problem at hand, the trade off you need between elegance and performance, and the amount of data you are processing. Iterative solutions will generally perform a little faster as they scale up because there is less overhead from stack manipulation and function calls. Recursive solutions, depending on the problem, can often times be much more readable and understandable.

#2blueEbola

Posted 03 February 2012 - 03:32 AM

I am curious I was asked a question today that just irks me cause I didn't know the answer and I blanked out. Here is a sample code that I wrote to show you. There are tons of examples on it anyways I just can't seem to find the answer.

function factorial($factor) {$temp;
if ($factor <= 1) return 1; return$temp = $factor * factorial($factor - 1);
}
// Example use

echo factorial(3);


Doesn't really matter what language as long as it allows you to call the function in its function.

Anyways the question was what is the advantage and disadvantage of using this... I froze so bad! Anyone able to explain this to me there was no over the other. I can write it in a different language if you don't understand it, but I am sure that won't be the issue. Thanks in advance.

There are times when recursion makes a lot of sense and can give you an elegant algorithm. Namely when the problem at hand is nothing more than a series of extremely similar sub-problems. Printing out a binary tree in sorted order looks way better in recursive form than the equivalent iterative solution (Python code):

NOTE: don't hate if there are minor issues with either of these functions, I haven't tested them!

The recursive solution is far easier to understand (imo) than the iterative solution. The recursive solution implicitly takes care of the stack state for us, while the iterative solution has to implement it's own stack in order to operate in the same way. That makes the recursive solution much more elegant, but it's not without it's drawbacks. As Washu mentioned, compilers tend to optimize out recursive functions with "tail call optimization" -- which means that if the recursive call to the same function is the last expression in the function, the compiler can turn it into an iterative form behind the scenes and do away with a stack overflow from occurring for monstrous recursive call chains. In the above implementation we have two recursive calls and that is problematic: if the tree is big enough, our "print_binary_tree(tree.left)" call will dig deep into the tree will take up a lot of memory on the stack before it hits an exit condition.

Some languages impose a hard limit on the amount of non-tail optimized recursive calls you can do: I believe Python will stop you after your stack depth gets a couple thousand calls deep. Other languages that are less safe like C++ will let you go on until you receive a stack overflow exception. Some compiled languages will even give you a warning when they detect that a recursive method is not optimized for tail call recursion.

At that point you have a few choices: you can rewrite your recursive function to utilize tail call optimization by making the only recursive call the last expression in the function, or you can just scrap it and rewrite it iteratively. The iterative solution can maintain it's stack in a memory space (such as the heap) that can grow much larger as needed. Rewriting the above recursive print_binary_tree function to utilize tail call optimization would look like this:

It does basically what the iterative solution does, except without the while loop. I think it's a bit prettier than the iterative solution, but the difference is negligible.

What you choose to do will depend entirely on the problem at hand, the trade off you need between elegance and performance, and the amount of data you are processing. Iterative solutions will generally perform a little faster as they scale up because there is less overhead from stack manipulation and function calls. Recursive solutions, depending on the problem, can often times be much more readable and understandable.

#1blueEbola

Posted 03 February 2012 - 03:29 AM

I am curious I was asked a question today that just irks me cause I didn't know the answer and I blanked out. Here is a sample code that I wrote to show you. There are tons of examples on it anyways I just can't seem to find the answer.

function factorial($factor) {$temp;
if ($factor <= 1) return 1; return$temp = $factor * factorial($factor - 1);
}
// Example use

echo factorial(3);


Doesn't really matter what language as long as it allows you to call the function in its function.

Anyways the question was what is the advantage and disadvantage of using this... I froze so bad! Anyone able to explain this to me there was no over the other. I can write it in a different language if you don't understand it, but I am sure that won't be the issue. Thanks in advance.

There are times when recursion makes a lot of sense and can give you an elegant algorithm. Namely when the problem at hand is nothing more than a series of extremely similar sub-problems. Printing out a binary tree in sorted order looks way better in recursive form than the equivalent iterative solution (Python code):

NOTE: don't hate if there are minor issues with either of these functions, I haven't tested them!

The recursive solution is far easier to understand (imo) than the iterative solution. The recursive solution implicitly takes care of the stack state for us, while the iterative solution has to implement it's own stack in order to operate in the same way. That makes the recursive solution much more elegant, but it's not without it's drawbacks. As Washu mentioned, compilers tend to optimize out recursive functions with "tail call optimization" -- which means that if the recursive call to the same function is the last expression in the function, the compiler can turn it into an iterative form behind the scenes and do away with a stack overflow from occurring for monstrous recursive call chains. In the above implementation we have two recursive calls and that is problematic: if the tree is big enough, our "print_binary_tree(tree.left)" call will dig deep into the tree will take up a lot of memory on the stack before it hits an exit condition.

Some languages impose a hard limit on the amount of non-tail optimized recursive calls you can do: I believe Python will stop you after your stack depth gets a couple thousand calls deep. Other languages that are less safe like C++ will let you go on until you receive a stack overflow exception. Some compiled languages will even give you a warning when they detect that a recursive method is not optimized for tail call recursion.

At that point you have a few choices: you can rewrite your recursive function to utilize tail call optimization by making the only recursive call the last one, or you can just scrap it and rewrite it iteratively. The iterative solution can maintain it's stack in a memory space (such as the heap) that can grow much larger as needed. Rewriting the above recursive print_binary_tree function to utilize tail call optimization would look like this:

It does basically what the iterative solution does, except without the while loop. I think it's a bit prettier than the iterative solution, but the difference is negligible.

What you choose to do will depend entirely on the problem at hand, the trade off you need between elegance and performance, and the amount of data you are processing. Iterative solutions will generally perform a little faster as they scale up because there is less overhead from stack manipulation and function calls. Recursive solutions, depending on the problem, can often times be much more readable and understandable.

PARTNERS