algorithm - recursivo - ¿En qué se diferencia la recursión estructural de la recursión generativa?

recursividad java

Question

La descripción de la recursión generativa en Wikipedia es clara para mí, pero estoy confundido acerca del concepto de recursión estructural.

¿Alguien puede explicar si una función que calcula el número n de Fibonacci y una función que calcula factorial de 1 a N será estructural o generativa?

Answer 1

La diferencia clave entre la recursión estructural y la generativa es que un procedimiento recursivo obtiene los datos en los que trabaja y cómo los procesa. Específicamente, para la recursión estructural, se realiza una llamada recursiva en un subconjunto de los datos de entrada originales. Mientras que para la recursión generativa, se realiza una llamada recursiva sobre los datos que se construyeron / calcularon a partir de los datos de entrada originales.

Por ejemplo, si desea contar el número de elementos en una lista vinculada, puede hacer lo siguiente:

int NumberOfNodes(ListNode* node) {
    if (node == nullptr) return 0;
    return 1 + NumberOfNodes(node->next);
}

Aquí, la llamada recursiva a NumberOfNodes se está haciendo en el node->next , que es una parte de la entrada original que ya existía. En este caso, la recursión funciona al desglosar la entrada en partes más pequeñas, y luego recurrir en las piezas más pequeñas.

De manera similar, este código para buscar un valor BST en un valor sería una recursión estructural, ya que las llamadas recursivas son a subpartes de la entrada original:

TreeNode* Find(TreeNode* root, DataType value) {
    if (root == nullptr) return nullptr;
    if (value < root->value) return Find(root->left, value);
    else return Find(root->right, value);

El término "recursión estructural" proviene del hecho de que estas estructuras (listas, BST, etc.) se pueden definir recursivamente:

• Una lista es nada o una celda seguida de una lista.
• Un árbol binario es nada o un nodo con dos árboles binarios como hijos.

Al hacer una recursión estructural, está "deshaciendo" la operación a partir de la cual estas estructuras se construyen una a la otra. Por ejemplo, la función NumberOfNodes "deshace" la construcción de tomar un nodo y añadirlo a una lista existente. El operador Find "deshace" la operación de pegar un nodo a otros dos árboles. Por lo tanto, es fácil ver por qué estas funciones tienen que terminar; eventualmente, "deshace" todas las operaciones que se realizaron para construir el objeto en primer lugar, y la recursión se detiene.

Por otro lado, considere Quicksort, que hace lo siguiente:

1. Elige un pivote.
2. Cree tres listas nuevas: uno de todos los elementos menos que el pivote, uno de todos los elementos más grande que el pivote y uno de todos los elementos igual al pivote.
3. Ordenar recursivamente la primera y la segunda de estas listas.
4. Concatene la lista de valores más pequeños, iguales y más grandes.

Aquí, las llamadas recursivas se están realizando en arreglos más pequeños que no formaban parte de la entrada original; las listas tenían que crearse a partir de los datos. (Normalmente, una implementación reutilizaría el espacio para estas listas, pero no se garantizaba que esas sublistas existieran directamente en la entrada).

Esta distinción es borrosa cuando se trata de números naturales. Normalmente, los números naturales se definen recursivamente de la siguiente manera:

• 0 es un número natural.
• Si n es un número natural, n + 1 es un número natural.
• Nada más es un número natural.

Bajo esta definición, el número n es una "parte" de n + 1. Por lo tanto, ¡este código recursivo para calcular n! es recursion estructural

int Factorial(int n) {
    if (n == 0) return 1;
    return n * Factorial(n - 1);
}

Esto es una recursión estructural, porque el argumento n - 1 era una "parte" de la entrada original n.

De manera similar, según esta definición, el cómputo del número n de Fibonacci cuenta recursivamente como recursión estructural:

int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Esto se considera recursión estructural porque n - 1 es una parte de n (formada por "deshacer" el +1) y n - 2 es una parte de n - 1 (nuevamente formada por "deshacer" el +1).

Por otro lado, este código para calcular gcd se consideraría recursión generativa, en lugar de recursión estructural:

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

El razonamiento es que dado que a % b se "calcula" a partir de a y b , en lugar de formarse por "deshacer" un cierto número de operaciones +1, se generan los datos.

La razón por la cual la recursión generativa es diferente de la recursión estructural es que no hay garantía de que termine. Por ejemplo, piensa en esta función:

int BadTimes(int a, int b) {
    if (a == 0 && b == 0) return 0;
    return BadTimes(a * 2, b - 1);
}

Esta función recursiva generativa nunca termina: a sigue creciendo, aunque b sigue haciéndose más pequeña.

Honestamente, nunca antes había oído hablar de esta distinción y imparto cursos de matemática y programación discretas. No me preocuparía demasiado al respecto, a menos que alguien requiera que sepas la diferencia.

¡Espero que esto ayude!