Qual é a diferença entre "recursão" e "auto-referência"?

Os artigos da Wikipedia são avançados demais para eu entender. Alguém poderia me dar uma explicação simples, por favor?

O contexto dos dois termos é geralmente diferente.

A auto-referência está no contexto dos dados - você tem um tipo de dados que contém uma referência a algo do mesmo tipo.

A recursiva está no contexto do código - você tem uma função ou procedimento que se chama.

Exemplo:

def factorial(n):
if n == 1:
    return 1
else:
    return n * factorial(n-1)

Aqui está uma função recursiva (em C):

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

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

    return result;
}

Essas duas chamadas para fibonacci()dentro da fibonacci()função são chamadas recursivas .

Aqui está uma estrutura de dados auto-referencial :

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

O primeiro elemento,, dataé apenas um ponteiro para algum tipo de dado. O segundo elemento,, nexté um ponteiro para outra ListNodeestrutura. Se você tiver duas ou mais ListNodeestruturas, poderá definir o nextponteiro de uma para o endereço de outra, e assim por diante, e então terá uma lista vinculada . A estrutura é auto-referencial porque a definição da estrutura se refere a si mesma. Se você quiser ficar realmente louco, você pode fazer o seguinte:

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

Agora você tem um tipo diferente de auto-referência - não é apenas a definição struct ListNodeque se refere a si mesma ... você definiu o nextponteiro nodepara apontar para nodesi mesmo. Esta é uma lista vinculada circular que contém apenas um elemento. Bonito, mas não muito útil. Menciono isso porque é um tipo de auto-referência, mas não é o que as pessoas geralmente querem dizer quando falam sobre tipos de dados auto-referenciais.

Espera-se que as recursões, principalmente as úteis, sejam encerradas após certo número de procedimentos, no sentido de que há algum valor inicial. a menos que você tenha uma recursão ruim que é inútil.

As auto-referências, por si só, não são exatamente recursões, mas podem ser mostradas como recursivas, caso em que geralmente nunca terminam.

Recursão implica ação.

Exemplos:

• uma função que se chama
• uma regex executando uma correspondência * ou + (ou seja, repetitiva)

Tecnicamente, a recursão deve ter um estado de saída, mas não é um requisito.

A auto-referência implica estrutura.

Ex. Um método de instância que faz referência ao objeto ao qual está anexado.

A recursão requer algo para processar através da chamada do mesmo processo (geralmente com parâmetros diferentes). Mesmo que você frequentemente use funções e essas funções se autodenominam, elas tecnicamente entram em uma nova etapa que, por acaso, parece com o local de onde elas vieram.

Auto-referência significa que algo se refere a si mesmo. As classes podem ser autorreferenciais usando this, mas isso não é significativamente recursivo.