If a class C contains a recursive method m(), then class C is part of a recursive data structure.


A class with a recursive method represents part of a recursive data structure


A class having a recursive method does not imply that it is part of a recursive data structure

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);

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.

Stay up-to-date

Follow us on  twitter to hear about new misconceptions.