RecursiveMethodImpliesRecursiveType

Correction

Here is what's right.

To be part of a recursive data structure, there needs to be a recursive dependency (a cycle) through the fields (instance variables) of the class.

A value of that class needs to (directly or indirectly) refer to a value of that class.

Class R below represents a recursive data structure (but has no recursive method):

class R {
  R f;
}

Class N below is not part of a recursive data structure (even though it contains the recursive method sum):

class N {
  int sum(int n) {
    return n==0 ? 0 : 1 + sum(n - 1);
  }
}

Value

How can you build on this misconception?

Seeing recursive data structures and recursive computation as closely related is actually a pretty good idea.

Recursive data structures and recursive methods go together quite well. This “collaboration” leads to structural recursion: a recursive method traverses a recursive data structure, and the recursive computation is driven by the recursive data structure. Common examples of structural recursion are traversal algorithms for lists (e.g., add up elements in a linked list) or trees (e.g., find a value in a binary tree).

Structural recursion is simpler than generative recursion, where the recursive computation is not driven by a recursive data structure. Common examples of generative recursion are the Fibonacci sequence, factorial, or the Towers of Hanoi.