Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# recursion??

Posted on 2000-04-26
Medium Priority
171 Views
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
Question by:beachbumm
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 16

Accepted Solution

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

ID: 2751693
0

## Featured Post

Question has a verified solution.

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

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…
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…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them 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.
###### Suggested Courses
Course of the Month5 days, 17 hours left to enroll