Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
2  
they're not really comparable terms. recursion refers to a function calling itself whereas self-reference refers to an object referencing itself. –  Jakob Weisblat Jan 4 '13 at 2:27
2  
@GerryMyerson would it be correct to say recursion calls itself; while self-reference refers to itself? –  skullpatrol Jan 4 '13 at 3:53
1  
@skullpatrol essentially yes, but I feel like you are missing a fundamental difference - they cannot apply to the same type of thing. –  Jakob Weisblat Jan 4 '13 at 3:57
1  
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. –  Jakob Weisblat Jan 4 '13 at 14:37
1  
@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. –  Caleb Jan 4 '13 at 22:23

5 Answers 5

up vote 11 down vote accepted

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.

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

share|improve this answer
    
Thank you, as always context fixes meaning. –  skullpatrol Jan 4 '13 at 9:26
    
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. –  skullpatrol Jan 4 '13 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. –  jmoreno Jan 5 '13 at 9:12

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.

share|improve this answer

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.

share|improve this answer
    
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? –  skullpatrol Jan 4 '13 at 5:35
2  
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. –  Caleb Jan 4 '13 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! –  Andres F. Jan 4 '13 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. –  Caleb Jan 4 '13 at 21:03
    
@Caleb Oops, sorry. If you are saying they are very close in meaning, then we agree and I misunderstood you! –  Andres F. Jan 4 '13 at 21:09

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.

share|improve this answer
    
So recursion requires a process via calling the same process, while self-reference is the "calling-of-itself"? –  skullpatrol Jan 4 '13 at 2:41
    
@skullpatrol - no. Self reference requires no calling what so ever. –  Telastyn Jan 4 '13 at 3:05
    
So recursion requires a process via calling the same process, while self-reference is the "referencing-of-itself"? –  skullpatrol Jan 4 '13 at 3:12

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.

share|improve this answer
5  
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 '13 at 0:58
5  
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 '13 at 1:42
2  
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 '13 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? –  skullpatrol Jan 4 '13 at 5:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.