1

I noticed that every fundamental data structure in Computer Science seems recursive in nature. e.g. Graphs, Lists, Arrays, Sets, etc.

Why is that? Is there some fundamental reason? Is it because it's easier to prove the properties of recursive data structures via induction?

vg1
  • 21
  • 3
  • It doesnt have to be, you can write it in a loop too. it is just that the pointer of the struct A, has to be inside struct A. – Saran-san Aug 28 '13 at 02:10
  • It matches the way we solve lots of problems in real-life: http://stackoverflow.com/questions/717725/understanding-recursion – dcaswell Aug 28 '13 at 02:19
  • Arrays and sets definitely aren't recursive in nature (though some set implementations may involve recursive records). In the case of sets, even the mathematical concept they are strongly based on (also called sets) is non-recursive too. Note that an *algorithm* can still be amendable to proof by induction even if the data structure isn't (as an example, consider insertion sort on an array). –  Aug 28 '13 at 02:33
  • @delnan: Sorry for the late reply! Could one argue that sets are recursive in nature because a subset is still a set? Or a subarray is still an array? – vg1 Aug 31 '13 at 12:00
  • @vg1 I'd say that makes *subsets* and *subarrays* recursively defined, or equivalently that one can think about these operations recursively. And of course this means many algorithms can be thought of as recursive. But the *definitions* of arrays and sets are just a flat "bunch of values". –  Aug 31 '13 at 12:03

0 Answers0