Solved

recursion??

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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

679 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