Thread: Recursion

  1. #1
    Registered User
    Join Date
    Apr 2015
    Posts
    438

    Recursion

    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; 5 Days Ago at 09:45 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,147
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    3,472
    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

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    36,745
    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.

  5. #5
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    539
    Quote Originally Posted by Salem View Post
    Follow this link for a practical demonstration.
    What's the stopping condition? I kept following that link and didn't know when to stop!

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,620
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursion
    By mikeman in forum C++ Programming
    Replies: 4
    Last Post: 03-29-2010, 12:26 PM
  2. Recursion
    By ChoCo in forum C Programming
    Replies: 3
    Last Post: 12-10-2009, 06:39 AM
  3. Recursion help please?
    By FusedOut in forum C Programming
    Replies: 4
    Last Post: 09-07-2003, 06:01 AM
  4. Recursion
    By Drew in forum C++ Programming
    Replies: 5
    Last Post: 08-21-2003, 06:20 PM
  5. recursion
    By condorx in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2002, 09:54 AM

Tags for this Thread