Recursive data structures
A recursive data structure contains references to itself, such as a list or tree. These types of structures are dynamic data structures where the structure can theoretically grow to an infinite length.
The recursive nature of this data structure lends itself to recursive algorithms. Examples of recursive data structures include:
- Linked lists
- Trees
- Filesystems
- Graph
It is sometimes thought that recursive methods work differently from regular methods. They don't. They both simply return when they are completed. A problem that can be solved using iteration can be solved using recursion. A problem that can be solved using recursion can be solved using iteration.
A recursive solution will typically take more space than an iterative solution. Each time a method is called, an activation record is created for the method. This activation record will contain its parameters and any local variables as is detailed in Understanding the program stack. An iterative solution will...
