Solved

recursion??

Posted on 2000-04-26
2
165 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 10 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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

746 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now