# What is the difference between "recursion" and "self-reference"?

The wikipedia articles are too advanced for me to understand, could someone give me a simple explanation please?

• they're not really comparable terms. `recursion` refers to a function calling itself whereas `self-reference` refers to an object referencing itself. Jan 4, 2013 at 2:27
• @GerryMyerson would it be correct to say recursion calls itself; while self-reference refers to itself? Jan 4, 2013 at 3:53
• @skullpatrol essentially yes, but I feel like you are missing a fundamental difference - they cannot apply to the same type of thing. Jan 4, 2013 at 3:57
• no. Self-reference refers to an object refetrencing itself (see wikipedia's article on OOP) wheras recursion refers to a function, or method, not an object. Jan 4, 2013 at 14:37
• @Jake223 I know where you're coming from, but you could also say that a structure like a linked list is recursively defined (the definition has a base case and an recursive step), and there's no doubt that recursive functions are self-referential. Jan 4, 2013 at 22:23

The context of the two terms is generally different.

Self referencing is in the context of data -- you have a data type that contains a reference to something of the same type.

Recursive is in the context of code -- you have a function or procedure that calls itself.

Example:

``````def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
``````
• Here are the two tag definitions on Stack Overflow: Recursion in computer science is a method of problem solving where the solution to a problem depends on solutions to smaller instances of the same problem. Self-reference is the ability of a program (or logical sentence) to refer to itself, either directly or indirectly. Jan 4, 2013 at 21:12
• And for tags, that seems about right. You don't want to get into odd corner cases for a tag. And it's probably about the level you want to think of now as well. Jan 5, 2013 at 9:12

Here's a recursive function (in C):

``````unsigned int fibonacci(unsigned int n)
{
unsigned int result = 1;

if (n > 1)
result = fibonacci(n - 1) + fibonacci(n - 2);

return result;
}
``````

Those two calls to `fibonacci()` inside the `fibonacci()` function are recursive calls.

Here's a self-referential data structure:

``````struct ListNode {
char *data;
struct ListNode *next;
}
``````

The first element, `data`, is just a pointer to some sort of data. The second element, `next`, is a pointer to another `ListNode` structure. If you have two or more `ListNode` structures, you can set the `next` pointer of one to the address of another, and so on, and you then have a linked list. The structure is self-referential because the definition of the structure refers to itself. If you want to get really crazy, you could do this:

``````struct ListNode *node = malloc(sizeof(struct ListNode));
node->data = someString;
node->next = node;
``````

Now you've got a different kind of self-reference -- it's not just the definition of `struct ListNode` that refers to itself... you've set the `next` pointer of `node` to point to `node` itself. This is a circular linked list containing only one element. Cute, but not very useful. I mention it because it's a kind of self-reference, but it's not what people usually mean when they talk about self-referential data types.

• Is it correct to say that recursion is a special case of self-reference where the object being referred to (or called) is a function? Jan 4, 2013 at 5:35
• Sure, you could say that a recursive call is a form of self reference. Sometimes the terms are nearly interchangeable, although not with respect to code. For example, most people would call "GNU" a "recursive acronym" because it stands for "GNU is Not Unix", but nobody would say that you were wrong if you called it a "self-referential acronym" instead. Jan 4, 2013 at 5:54
• @Caleb This is not a particularly good example, because List is a recursive data type. So you are actually showing another example of recursion! Jan 4, 2013 at 20:26
• @AndresF. Can you give an example of a self-referential data structure that's not a recursive data type? Sources like this and this use the term 'self-referential' for structures like linked lists while others use 'recursive'. If my answer fails to make a clear distinction between the terms, it's because the terms aren't exactly synonymous, but are very close in meaning. Jan 4, 2013 at 21:03
• @Caleb Oops, sorry. If you are saying they are very close in meaning, then we agree and I misunderstood you! Jan 4, 2013 at 21:09

Recursions, mostly useful ones, are expected to terminate after certain number of procedures in a sense that there is some initial value. unless you have a bad recursion that is useless.

Self References, are by themselves not exactly recursions but can be shown to have recursion in which case they generally never terminate.

• If you define recursion as a construction being carried over a well-founded relation, then the fact a recursion does not terminate corresponds to an infinite decreasing sequence -- and therefore the self-referential "recursion" is not at all a recursion. This is much like how an algorithm is required to stop at some point.
– Asaf Karagila
Jan 4, 2013 at 0:58
• What about this statement: "This sentence has five words." It's self-referential, but I don't see any nonterminating recursion. I also don't think recursion generally has to involve self-reference. If you compile a recursive C function into binary machine code, the machine code doesn't have any self-reference in it. I think the most you can say is that a terminating self-reference is one possible way of defining a recursion.
– Ben Crowell
Jan 4, 2013 at 1:42
• Yes, this my explanation is by no way perfect. I am just trying to simplify in case "OP is trying to interpret some self references as recurances." I no way mean self references are always non terminating recursions.
– user1710036
Jan 4, 2013 at 1:50
• Is it correct to say that recursion is a special case of self-reference where the object being referred to (or called) is a function? Jan 4, 2013 at 5:32

Recursion implies action.

Examples:

• a function that calls itself
• a regex performing a * or + (ie repetitive) match

Technically, recursion should have an exit state but it's not a requirement.

Self-reference implies structure.

Ex. An instance method referencing the object it's attached to.

Recursion requires something to process via calling the same process (often with different parameters). Even though you're often using functions and those functions call themselves, they technically enter a new step that just happens to look like the place they just came from.

Self-Reference means that something refers to itself. Classes can be self-referential by using `this`, but that's not meaningfully recursive.

• So recursion requires a process via calling the same process, while self-reference is the "calling-of-itself"? Jan 4, 2013 at 2:41
• @skullpatrol - no. Self reference requires no calling what so ever. Jan 4, 2013 at 3:05
• So recursion requires a process via calling the same process, while self-reference is the "referencing-of-itself"? Jan 4, 2013 at 3:12