Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

recursion??

Posted on 2000-04-26
2
Medium Priority
?
172 Views
Last Modified: 2010-04-15
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
0
Comment
Question by:beachbumm
2 Comments
 
LVL 16

Accepted Solution

by:
imladris earned 40 total points
ID: 2751652
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 Comment

by:beachbumm
ID: 2751693
thanks imladris!!
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

927 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question