The subject may seem little bit contradictory. Recursive approach is very convenient when doing search or traversals in a tree structure (e.g. binary tree).
Use of recursion in an algorithm has both advantages and disadvantages. The main advantage is usually simplicity. The main disadvantage is often that the algorithm may require large amounts of memory if the depth of the recursion is very large. High memory consumption is due to large function call number (recursion means that function calls itself multiple times).
Every function call results in thread's stack memory consumption. Default stack size is 1 Mb. So, with high recursion depth there is a risk to run out of memory.
Next time I'll present recursive and non-recursive approaches to binary tree traversals.
Wednesday, September 19, 2007
Why Avoid Recursion For Tree Structures
Опубліковано V о 9/19/2007 11:21:00 AM
Мітки: Algorithms
Subscribe to:
Post Comments (Atom)
Posts
You won't have function calls if your recirsive procedure is tail-recursive and your compiler optimizes it.
ReplyDeleteAtually, the scheme language encourages you to only use recursion for iterating over things (the standard says that all scheme compilers need to optimize tail recursive calls). Good Lisp compilers do that too. Even the most recent version of gcc will also do that, so if you have a tail-recursive function in your C or C++ program, you won't be wasting stack space.
You can do some cool tricks to turn non-tail recursive functions into tail-recursive...
So, there is nothing wrong with recursion. It may or may not be the most natural way to express your algorithm -- that depends on the situation.
You need to qualify your statement just a little bit.
ReplyDeleteIf you are programing in a language that doesn't support tail recursion, then yes it can use a lot of memory.
But if you are using a tail recursive language, and write your function correctly, the recursive function doesn't use any more memory then the initial function call.
Wikipedia explains it nicely:
http://en.wikipedia.org/wiki/Tail_recursion
Actualy, I was thinking of a low level language and not functional one.
ReplyDeleteTail-recusion is nice when you have single recusive call. But what will happen when algorithm has to use two recursive calls. E.g. binary tree has two nodes: left and right. So one of the recursive calls will not be last during tree traversal process.
To completely avoid recusion while doing binary tree traversal one has to use additional data structures like stacks or lists to track visited nodes. Or tree node has to have metadata (now its parent and have "visited" flag).