•
•
•
•
What is DaniWeb IT Discussion Community?
You're currently browsing the C++ section within the Software Development category of DaniWeb, a massive community of 397,810 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 2,515 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.
Please support our C++ advertiser:
Views: 2426 | Replies: 10
 |
•
•
Join Date: Oct 2006
Location: New York City
Posts: 2,553
Reputation: 
Rep Power: 7
Solved Threads: 1
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:
Rep Power: 2
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: 3,462
Reputation: 
Rep Power: 16
Solved Threads: 138
•
•
•
•
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 9:45 pm.
•
•
Join Date: Dec 2006
Posts: 209
Reputation:
Rep Power: 2
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
Location: India
Posts: 6,806
Reputation:
Rep Power: 23
Solved Threads: 338
•
•
•
•
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."
"Working a real job is a win if you're lazy, greedy, or unmotivated. If you're average, you fit right in. And if you're above average, the basic terms of employment and premise of the arrangement is against your interests."
"Working a real job is a win if you're lazy, greedy, or unmotivated. If you're average, you fit right in. And if you're above average, the basic terms of employment and premise of the arrangement is against your interests."
•
•
Join Date: May 2006
Location: Bellevue, WA
Posts: 1,548
Reputation:
Rep Power: 8
Solved Threads: 51
•
•
•
•
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.
I'd take stable-matching/marriage off that list, since it's much easier to do in a loop. Min-max would be a suitable replacement, however, it might be too complex for a basic example.
@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
Location: India
Posts: 6,806
Reputation:
Rep Power: 23
Solved Threads: 338
•
•
•
•
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."
"Working a real job is a win if you're lazy, greedy, or unmotivated. If you're average, you fit right in. And if you're above average, the basic terms of employment and premise of the arrangement is against your interests."
"Working a real job is a win if you're lazy, greedy, or unmotivated. If you're average, you fit right in. And if you're above average, the basic terms of employment and premise of the arrangement is against your interests."
•
•
Join Date: Oct 2006
Location: New York City
Posts: 2,553
Reputation:
Rep Power: 7
Solved Threads: 1
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
Location: Bellevue, WA
Posts: 1,548
Reputation:
Rep Power: 8
Solved Threads: 51
•
•
•
•
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
Location: India
Posts: 6,806
Reputation:
Rep Power: 23
Solved Threads: 338
•
•
•
•
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."
"Working a real job is a win if you're lazy, greedy, or unmotivated. If you're average, you fit right in. And if you're above average, the basic terms of employment and premise of the arrangement is against your interests."
"Working a real job is a win if you're lazy, greedy, or unmotivated. If you're average, you fit right in. And if you're above average, the basic terms of employment and premise of the arrangement is against your interests."
|
•
•
•
•
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
•
•
•
•
•
•
•
•
DaniWeb C++ Marketplace
Linear Mode
Other Threads in the C++ Forum
- Previous Thread: need help pls
- Next Thread: g++ allegro linking
