Hey!
In abbreviation I know what's recursion and how it's working on computer, my question is I didn't understand the term of "Recursion is about traversing(assuming in binary tree)" can someone give me analogy of how recursion is really traversing?
traversing I think means calling all other sides and returning to the caller, so it's called traversing ....any analogy of real life about?!
sorry about that but to be more sensible to the term of recursion !
Last edited by RyanC; 12-06-2018 at 09:45 AM.
I think you're over-thinking this. If you understand recursion, then say, you could write a recursive function to do something with a binary tree that would involve traversing the tree in some way. That's it. Don't over think. You shouldn't need an analogy when terms like "tree" and "traverse" are already metaphors.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
In recursion, the first thing that I normally think about is the stopping condition(s).
Tim S.
"...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson
Recursion is used for self-similar problems.
A sub-tree of a tree still looks like a tree.
factorial(N) is N*factorial(N-1)
As stahta01 says, you just need to figure out what the really simple step is.
For a tree, it's an empty tree.
For factorial, it's factorial(0).
Follow this link for a practical demonstration.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
What's the stopping condition? I kept following that link and didn't know when to stop!
Recursion isn't always about traversing. The factorial example is mathematical example of recursion, whereas traversal usually implies following some type of data path such as a linked list (recursion not needed for this) or following a tree or other nested type of structure, where recursion is a useful way to "traverse" such a nested structure depth first by saving references or pointers to parent nodes on the stack. There are also cases where a traversal doesn't involve recursion or a stack, such as a breadth first traversal of a tree which typically uses a queue. It's also possible to do an "in-order" traversal of a binary tree without recursion, by modifying the pointers, known as Morris Traversal.
