• C

# recursion??

heres another question i disagree with my friend on...he says that recursion might be thought of as automatic manipulation of system data structure known as the run time to be a linked list. i disagree and say it is a tree. am i right or wrong on this assumption? any help would be helpful
###### Who is Participating?

Commented:
Well, I don't know if this is helpful help, but here goes.

Recursion perse, is neither a list nor a tree in my opinion. The classic example of recursion is the definition of factorial. The value of n factorial is usually explained along the lines:

n!=n*(n-1)!

and it also needs to be pointed out that the effort stops when n is 1. In and of itself such a "recursion" doesn't look like a list or a tree to me. The essence of a recursive definition or operation is its selfreferential nature.

The other question one could ask is how is recursion implemented by various programming languages. It is implemented through the use of a stack. When a function or method calls itself (which is what makes it a recursive function or method) it pushes arguments and a return address onto the stack and then execution goes to the beginning of the function again.

If you were looking at an implementation of calculating factorial that could look kind of like a list (since it would call itself for progressively smaller values of n, until it reached one, then unwind straight back up).

On the other hand if you were looking at a function that does an in-order traverse of a binary tree, it would call itself, going down the left side of the tree, until it hit a leaf, then go back up, then down along the right side of nodes etc. I.e. it would be bobbing up and down the tree. That might look more like a tree to you.

But, it's really based on a stack.

0

Author Commented: