454,912 Members | 1,247 Online
+ 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 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
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" 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.