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

Question

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

Answer 1

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)

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.