Recursivity

[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.

[Ravalon]

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.

Recursion and OOP are independent. OOP is more of a structuring method to make medium and large projects easier to manage. Recursion is a problem solving pattern used when a tough problem can be broken down until it's easy.

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. :)

[Dave Sinkula]

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.

Perhaps the data structures and algorithms associated with searching and sorting are better examples?
Optimized quicksort implementation

[Ravalon]

Perhaps the data structures and algorithms associated with searching and sorting are better examples?

• Recursive AVL Binary Search Tree
• Optimized quicksort implementation

Good examples, but I'm not sure they're better. ;) 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. ;)

[~s.o.s~]

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.

OOP is basically a programming paradigm, a framework, more tightly coupled with the field of Software engineering and Software design than with actual programming . Smart data structures with dumb functions -- that what many people know OOP with.

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.

[Infarction]

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.

[~s.o.s~]

As mentioned earlier, the FIbonnacci sequence is a classic example of recursion.

...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. 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.

[mattyd]

Thanks to everyone who has replied; this indeed has given me much to look into. ;) I appreciate your time and help.

MattyD

[Infarction]

...which even can be solved with a really simple loop.

The Fibonnacci sequence is defined as a recursive equation; adding memoization and making it iterative makes the calculaiton much faster. So yes, it can be solved with a loop. Any simple recursive function can. The reason I brough up stable matching as being non-recursive is because I've never encountered a recursive solution for it; for instance, the Gale-Shapley algorithm is typically presented just as a loop.

Since the langugages in which we program are normally turing complete, there is as such nothing which can only be solved using recursion.

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.

[~s.o.s~]

With the very notable exception of functional languages which use recursion as their way of creating an iterative procedure.

I guess I should have said the "languages in which I program"....

And I don't know for sure, but I don't think you can calculate the Ackermann function iteratively.

Though I am no expert on Mathematics, but the article says that Ackermann function can also be expressed iteratively and if it can be expressed iteratively, it can be solved iteratively.

[Infarction]

Though I am no expert on Mathematics, but the article says that Ackermann function can also be expressed iteratively and if it can be expressed iteratively, it can be solved iteratively.

Here's what it said:

The Ackermann function can also be expressed nonrecursively using Conway chained arrow notation:

As with most combinatorial symbologies, the definition is recursive.