- Forum
- General C++ Programming
- What are some recursive algorithms every
What are some recursive algorithms everyone should know
For example Binary search, a recursive algorithm that most programmers know,
what are some other examples?
what are some other examples?
I have heard of
In other words it is not important whether something is recursive.
The important thing is to understand why some task is both easier to write and maintain (and more efficient) with recursion than with iteration.
Granted, some people learn by examples.
std::sort and std::binary_search, but I don't need to know whether they are recursive or not; that knowledge wouldn't affect how I use them.In other words it is not important whether something is recursive.
The important thing is to understand why some task is both easier to write and maintain (and more efficient) with recursion than with iteration.
Granted, some people learn by examples.
you won't need to write your own search or sort anymore, but understanding those lets you do other things that are similar. Honesty for sorting I believe the reverse... some small systems can't handle recursion or lack the stack to do a big piece of data, so its good to know a hot non recursive sort eg shell. Not every language is as rich as C++ so you may have to craft these things in some languages for yourself.
The things to know maybe more theoretical. Every recursive program can be solved with iteration or another way, but recursion often makes a smaller (if harder to understand at first) piece of code that greatly simplifies a problem, but if you understand the classic applications you can craft your own code as needed with less frustration.
some examples:
many tree algorithms are recursive. there is no tree STL in c++ that I know of, though you can build one easily from what IS there.
factorial. Its useless in and of itself (there are far better ways to get the numbers), but the algorithm is pretty much THE 'how recursion works for a simple problem' and should be understood by all.
the 8 queens problem (which was done in like 20 pages of code with iteration and 1 page with recursion, and its complex enough to get a feel for how-to-do-stuff).
in practice.... recursion is good in graphs as stated (and, really, trees are a type of graph). A lot of data is recursive 'by nature' such as xml or other parsers. C++ and other high level languages probably use recursion or could use it for some of the process to unravel hierarchical language elements. XML etc parsers already exist, of course, but you may find yourself with a similar class of problem...
it is also useful for some challenge/oddball string or math processing.. codechef type silly problems. Often the recursive part is 'looking at the data differently' eg processing it in reverse of the input order. Equation processing can be recursive, though sometimes its a case of looking for nails with your hammer.
The things to know maybe more theoretical. Every recursive program can be solved with iteration or another way, but recursion often makes a smaller (if harder to understand at first) piece of code that greatly simplifies a problem, but if you understand the classic applications you can craft your own code as needed with less frustration.
some examples:
many tree algorithms are recursive. there is no tree STL in c++ that I know of, though you can build one easily from what IS there.
factorial. Its useless in and of itself (there are far better ways to get the numbers), but the algorithm is pretty much THE 'how recursion works for a simple problem' and should be understood by all.
the 8 queens problem (which was done in like 20 pages of code with iteration and 1 page with recursion, and its complex enough to get a feel for how-to-do-stuff).
in practice.... recursion is good in graphs as stated (and, really, trees are a type of graph). A lot of data is recursive 'by nature' such as xml or other parsers. C++ and other high level languages probably use recursion or could use it for some of the process to unravel hierarchical language elements. XML etc parsers already exist, of course, but you may find yourself with a similar class of problem...
it is also useful for some challenge/oddball string or math processing.. codechef type silly problems. Often the recursive part is 'looking at the data differently' eg processing it in reverse of the input order. Equation processing can be recursive, though sometimes its a case of looking for nails with your hammer.
Last edited on
Topic archived. No new replies allowed.