 |  |  |  |  |  |  |  |
Recursivity
Please support our C++ advertiser: Intel Parallel Studio Home
 |
Hello:
I am interested in understanding recursivity; I have not knowingly used this much in my programming. I am reviewing certain areas of OOP in order to learn more and better about areas that I may not be fully understood yet. Recursivity is one of these areas. I understand the definition of the word, of course, but am having a bit of trouble finding good examples online or full tutorials on the subject in regards to OOP. Any help or direction would be greatly appreciated.
Thank-you in advance.
Matty D.
I am interested in understanding recursivity; I have not knowingly used this much in my programming. I am reviewing certain areas of OOP in order to learn more and better about areas that I may not be fully understood yet. Recursivity is one of these areas. I understand the definition of the word, of course, but am having a bit of trouble finding good examples online or full tutorials on the subject in regards to OOP. Any help or direction would be greatly appreciated.
Thank-you in advance.
Matty D.
•
•
Join Date: Dec 2006
Posts: 209
Reputation: 
Solved Threads: 15
Posting Whiz in Training
•
•
•
•
Originally Posted by mattyd 
Hello:
I am interested in understanding recursivity; I have not knowingly used this much in my programming. I am reviewing certain areas of OOP in order to learn more and better about areas that I may not be fully understood yet. Recursivity is one of these areas. I understand the definition of the word, of course, but am having a bit of trouble finding good examples online or full tutorials on the subject in regards to OOP. Any help or direction would be greatly appreciated.
Thank-you in advance.
Matty D.
Good examples are hard to come by when the examples are factorials, fibonacci calculations, and the towers of hanoi. :rolleyes: Factorials can be more easily solved with a simple loop, recursive fibonacci algorithms are usually too inefficient to show the beauty of recursion, and the towers of hanoi can be written easily with a simple loop.
I think the best example of recursion is one you use with almost every program.
A C/C++ compiler will probably be using recursive descent to parse your code because that makes it easier to handle an unknown amount of nesting for blocks. If you want to learn recursion where it's well used, some research on recursive descent parsing would go down smooth. It's hard to be humble when you're as gifted as I am at pretending to be an expert.
•
•
Join Date: Apr 2004
Posts: 4,452
Reputation: 
Solved Threads: 250
•
•
•
•
Originally Posted by Ravalon
Good examples are hard to come by when the examples are factorials, fibonacci calculations, and the towers of hanoi. :rolleyes: Factorials can be more easily solved with a simple loop, recursive fibonacci algorithms are usually too inefficient to show the beauty of recursion, and the towers of hanoi can be written easily with a simple loop.
Optimized quicksort implementation
Last edited by Dave Sinkula; Feb 2nd, 2007 at 10:45 pm.
"One of the methods used by statists to destroy capitalism consists in establishing controls that tie a given industry hand and foot, making it unable to solve its problems, then declaring that freedom has failed and stronger controls are necessary." --Ayn Rand
•
•
Join Date: Dec 2006
Posts: 209
Reputation:
Solved Threads: 15
Posting Whiz in Training
•
•
•
•
Originally Posted by Dave Sinkula
Perhaps the data structures and algorithms associated with searching and sorting are better examples?
Personally I never liked recursion for trees, and unlike recursive descent parsing, people like to go out of their way to minimize the recursion in quicksort. Like me, I think they just tolerate that last one that can't be removed without a stack. It's hard to be humble when you're as gifted as I am at pretending to be an expert.
•
•
Join Date: Jun 2006
Posts: 7,648
Reputation:
Solved Threads: 474
•
•
•
•
Originally Posted by mattyd
I am interested in understanding recursivity; I have not knowingly used this much in my programming. I am reviewing certain areas of OOP in order to learn more and better about areas that I may not be fully understood yet. Recursivity is one of these areas. I understand the definition of the word, of course, but am having a bit of trouble finding good examples online or full tutorials on the subject in regards to OOP. Any help or direction would be greatly appreciated.
Recursion is particulary a strong concept which is not only used in solving programming problems but also extensively in the field of Mathematics.
Eg. if we were asked to define what natural numbers are (you can't write down all of those ):
1. Natural numbers:
(a) 0 is a natural number.
(b) the successor of a natural number is a natural number.
Similarly the concept used in defining grammar in the BNF ( Bakus Naur Form).
Google for terms like Sierpinski curve, Knights tour, Travelling salesman problem, Stable Marriage problem and the Eight Queens problem for some applications of recursive problem solving techniques.
I don't accept change; I don't deserve to live.
Jo Tujhe Jagaaye, Nindein Teri Udaaye Khwaab Hai Sachcha Wahi.
Nindon Mein Jo Aaye Jise To Bhul Jaaye Khawab Woh Sachcha Nahi.
Khwaab Ko Raag De, Nind Ko Aag De
Jo Tujhe Jagaaye, Nindein Teri Udaaye Khwaab Hai Sachcha Wahi.
Nindon Mein Jo Aaye Jise To Bhul Jaaye Khawab Woh Sachcha Nahi.
Khwaab Ko Raag De, Nind Ko Aag De
•
•
Join Date: May 2006
Posts: 1,580
Reputation:
Solved Threads: 52
•
•
•
•
Originally Posted by ~s.o.s~
Google for terms like Sierpinski curve, Knights tour, Travelling salesman problem, Stable Marriage problem and the Eight Queens problem for some applications of recursive problem solving techniques.
@OP: recursivity is a useful tool for breaking down problems and handling them in a divide-and-conquer fashion. This won't always yield a more efficent result, but in some cases it does. The basic premise of recursion is that a function calls itself with a subset of its data, and solves a problem for that subset. When the 2nd call returns, the data may require some extra manipulation; other times, it'll have been handled during the recursive call anyways (see mergesort and quicksort respectively). As mentioned earlier, the FIbonnacci sequence is a classic example of recursion.
•
•
Join Date: Jun 2006
Posts: 7,648
Reputation:
Solved Threads: 474
•
•
•
•
Originally Posted by Infarction
As mentioned earlier, the FIbonnacci sequence is a classic example of recursion.
Since the langugages in which we program are normally turing complete, there is as such nothing which can only be solved using recursion. A real example of recursion would be the one in which the iterative solution would not be too apparent and even when such a solution is found, would be too complex. Recursive descent parser, like Raye mentioned, Backtracking problems still stand as a good examples.
Graphical representations of some of them using applets here.
I don't accept change; I don't deserve to live.
Jo Tujhe Jagaaye, Nindein Teri Udaaye Khwaab Hai Sachcha Wahi.
Nindon Mein Jo Aaye Jise To Bhul Jaaye Khawab Woh Sachcha Nahi.
Khwaab Ko Raag De, Nind Ko Aag De
Jo Tujhe Jagaaye, Nindein Teri Udaaye Khwaab Hai Sachcha Wahi.
Nindon Mein Jo Aaye Jise To Bhul Jaaye Khawab Woh Sachcha Nahi.
Khwaab Ko Raag De, Nind Ko Aag De
Thanks to everyone who has replied; this indeed has given me much to look into. I appreciate your time and help.
MattyD
I appreciate your time and help.MattyD
•
•
Join Date: May 2006
Posts: 1,580
Reputation:
Solved Threads: 52
•
•
•
•
Originally Posted by ~s.o.s~
...which even can be solved with a really simple loop.
•
•
•
•
Since the langugages in which we program are normally turing complete, there is as such nothing which can only be solved using recursion.
•
•
Join Date: Jun 2006
Posts: 7,648
Reputation:
Solved Threads: 474
•
•
•
•
Originally Posted by Infarction
With the very notable exception of functional languages which use recursion as their way of creating an iterative procedure.
•
•
•
•
And I don't know for sure, but I don't think you can calculate the Ackermann function iteratively.
I don't accept change; I don't deserve to live.
Jo Tujhe Jagaaye, Nindein Teri Udaaye Khwaab Hai Sachcha Wahi.
Nindon Mein Jo Aaye Jise To Bhul Jaaye Khawab Woh Sachcha Nahi.
Khwaab Ko Raag De, Nind Ko Aag De
Jo Tujhe Jagaaye, Nindein Teri Udaaye Khwaab Hai Sachcha Wahi.
Nindon Mein Jo Aaye Jise To Bhul Jaaye Khawab Woh Sachcha Nahi.
Khwaab Ko Raag De, Nind Ko Aag De
|
Other Threads in the C++ Forum
- Previous Thread: need help pls
- Next Thread: g++ allegro linking
| Thread Tools | Search this Thread |
Latest C++ Posts
- Today's Posts
- Unanswered Threads
Related Forum Features
Tag cloud for C++
api application array arrays based beginner binary bmp c++ c/c++ calculator char char* class classes code compile compiler console conversion convert count data delete deploy dll download dynamiccharacterarray email encryption error file format forms fstream function functions game givemetehcodez graph homeworkhelp iamthwee ifstream input int java lib library lines list loop looping loops map math matrix memory newbie news number numbertoword output pointer problem program programming project python random read recursion recursive reference return rpg search simple sorting spoonfeeding string strings struct temperature template templates text text-file tree url variable vector video visual visualstudio void win32 windows winsock wordfrequency wxwidgets
