By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,912 Members | 1,247 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,912 IT Pros & Developers. It's quick & easy.

Recusrion

P: n/a
Ken
Hello,

I have this recusrion code below I know how the looping works, but where I
get confused is with the return 1, How does it know to send the accumulated
value and not just returning the number 1 with any n input.

int recursion(int n)
{
if (n == 0) return 1;
else return n * recursion(n-1);
};
-Ken
Jul 23 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a
Ken wrote:
I have this recusrion code below I know how the looping works, but
where I get confused is with the return 1, How does it know to send
the accumulated value and not just returning the number 1 with any n
input.
int recursion(int n)
{
if (n == 0) return 1;
else return n * recursion(n-1);
};


Recursion cannot be explained, only shown. Take the 'else' part and
expand the contents. Pretend you're a compiler and you need to inline
the code in this function. (I know that recursive functions cannot be
inlined during compilation, just pretend you can and do it as if it is
during run-time)

V
Jul 23 '05 #2

P: n/a
Ken wrote:
Hello,

I have this recusrion code below I know how the looping works, but where I
get confused is with the return 1, How does it know to send the accumulated
value and not just returning the number 1 with any n input.

int recursion(int n)
{
if (n == 0) return 1;
else return n * recursion(n-1);
};


What's important is the 'n*recursion(n-1)' part, which does the actual
accumulation.

int main()
{
recursion(3);
}

does:

recursion(n=3)
return 3*recursion(2)
recursion(n=2)
return 2*recursion(1)
recursion(n=1)
return 1
return 2*1
return 3*2*1
return 6

Do it on a piece of paper if that's not clear enough. It's quite simple
once you understand it.
Jonathan

Jul 23 '05 #3

P: n/a

"Jonathan Mcdougall" <jo***************@gmail.com> wrote in message
news:11*********************@g44g2000cwa.googlegro ups.com...
Ken wrote:
Hello,

I have this recusrion code below I know how the looping works, but where I get confused is with the return 1, How does it know to send the accumulated value and not just returning the number 1 with any n input.

int recursion(int n)
{
if (n == 0) return 1;
else return n * recursion(n-1);
};


What's important is the 'n*recursion(n-1)' part, which does the actual
accumulation.

int main()
{
recursion(3);
}

does:

recursion(n=3)
return 3*recursion(2)
recursion(n=2)
return 2*recursion(1)
recursion(n=1)
return 1
return 2*1
return 3*2*1
return 6

Do it on a piece of paper if that's not clear enough. It's quite simple
once you understand it.
Jonathan


That said, it is always good to be cautious with recursions. Where both
iteration and recursion can be used, prefer iteration over recursion.

And that, of course, excludes educational or intentional exercises...

Ben
Jul 23 '05 #4

P: n/a
On Sun, 17 Jul 2005 10:48:49 +1000, benben wrote:

That said, it is always good to be cautious with recursions. Where both
iteration and recursion can be used, prefer iteration over recursion.


Uh, no. Do whatever is most natural given the algorithm you want to
express and let the compiler optimize everything into efficient machine
code. Handicapping yourself out of efficiency concerns is misguided
unless you have actually /profiled/ and /know/ it is unacceptably
inefficient to do things the natural way.
----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Jul 23 '05 #5

P: n/a
> Uh, no. Do whatever is most natural given the algorithm you want to
express and let the compiler optimize everything into efficient machine
code. Handicapping yourself out of efficiency concerns is misguided
unless you have actually /profiled/ and /know/ it is unacceptably
inefficient to do things the natural way.


Exactly! And how many times you find recursion more natural than iteration?
And how many times you find recursive code easier to maintain?

Regards,
Ben
Jul 23 '05 #6

P: n/a
On Sun, 17 Jul 2005 16:40:54 +1000, benben wrote:

Exactly! And how many times you find recursion more natural than iteration?
And how many times you find recursive code easier to maintain?


I find it easier quite often. When dealing with trees, for example,
recursion is really the only option that doesn't bend my brain. And
mathematical operations are often defined in terms of recursion instead of
iteration.
----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Jul 23 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.