recursion - ventajas - Diferencia entre retroceso y recursividad?

recursividad en programacion java

Question

¿Cuál es la diferencia entre retroceder y recurrencia? ¿Cómo funciona este programa?

void generate_all(int n)
 {
    if(n<1) printf("%s/n", ar);
    else{
            ar[n-1]=''0'';        //fix (n)th bit as ''0''
            generate_all(n-1);  //generate all combinations for other n-1 positions.
            ar[n-1]=''1'';        //fix (n)th bit as ''1''
            generate_all(n-1);  //generate all combinations for other n-1 positions.
    }

Answer 1

En mi entender, el retroceso es un algoritmo, como todos los otros algoritmos, como BFS y DFS, pero la recursión y la iteración son métodos, están en un nivel más alto que los algoritmos, por ejemplo, para implementar un DFS, puede usar la recursión , que es bastante intuitivo, pero también puede usar la iteración con una pila, o también puede pensar que la recursión y la iteración son solo métodos para respaldar sus algoritmos.

Answer 2

Esa pregunta es como preguntar cuál es la diferencia entre un automóvil y un DeLorean.

En la función de recursión se llama a sí mismo hasta que llega a un caso base.

Al retroceder utiliza recursividad para explorar todas las posibilidades hasta obtener el mejor resultado para el problema.

Puede ser un poco difícil de entender, adjunto algunos textos desde aquí :

"Conceptualmente, comienzas en la raíz de un árbol, el árbol probablemente tiene algunas hojas buenas y algunas malas, aunque puede ser que las hojas estén todas bien o mal. Quieres llegar a una buena hoja. En cada nodo , comenzando con la raíz, eliges uno de sus hijos para moverlo, y lo mantienes hasta que llegas a una hoja.

Supongamos que llega a una mala hoja. Puede retroceder para continuar la búsqueda de una buena hoja al revocar su elección más reciente y probar la siguiente opción en ese conjunto de opciones. Si te quedas sin opciones, cancela la opción que te trajo aquí y prueba con otra opción en ese nodo. Si terminas en la raíz sin opciones, no hay buenas hojas para encontrar ".

Esto necesita un ejemplo.

Tu fragmento de código es simplemente recursividad, ya que nunca regresas si el resultado no se ajusta a tu objetivo.

Answer 3

Recursion describe el llamado de la misma función en la que se encuentra. El ejemplo típico de una función recursiva es el factorial, es decir, algo así como

int fact(int n) {
    int result;
    if(n==1) return 1;
    result = fact(n-1) * n;
    return result;
}

Lo que ves aquí es que el hecho se llama a sí mismo. Esto es lo que se llama recursividad. Siempre necesita una condición que detiene la recursión. Aquí está if(n==1) combinado con el hecho de que n siempre disminuirá cada vez que se llame ( fact(n-1) )

Backtracking es un algoritmo que intenta encontrar una solución a los parámetros dados. Construye candidatos para la solución y abandona aquellos que no pueden cumplir con las condiciones. Un ejemplo típico para una tarea a resolver sería el Ocho Rompecabezas de Queens . Backtracking también se usa comúnmente en redes neuronales.

El programa que describes usa recursividad. Similar a la función factorial, disminuye el argumento en 1 y termina si n <1 (porque luego imprimirá ar lugar de hacer el resto).