¿Puede una función recursiva tener iteraciones / bucles?

He estado estudiando sobre funciones recursivas, y aparentemente, son funciones que se llaman a sí mismas y no usan iteraciones / bucles (de lo contrario, no sería una función recursiva).

Sin embargo, mientras navegaba por la web en busca de ejemplos (el problema recursivo de 8 reinas), encontré esta función:

private boolean placeQueen(int rows, int queens, int n) {
    boolean result = false;
    if (row < n) {
        while ((queens[row] < n - 1) && !result) {
            queens[row]++;
            if (verify(row,queens,n)) {
                ok = placeQueen(row + 1,queens,n);
            }
        }
        if (!result) {
            queens[row] = -1;
        }
    }else{
        result = true;
    }
    return result;
}

Hay un whilebucle involucrado.

... así que estoy un poco perdido ahora. ¿Puedo usar bucles o no?

Usted entendió mal la recursividad: aunque puede usarse para reemplazar la iteración, no hay absolutamente ningún requisito para que la función recursiva no tenga iteraciones internas en sí misma.

El único requisito para que una función se considere recursiva es la existencia de una ruta de código a través de la cual se llama a sí misma, directa o indirectamente. Todas las funciones recursivas correctas también tienen un condicional de algún tipo, que les impide "recurrir" para siempre.

Su función recursiva es ideal para ilustrar la estructura de la búsqueda recursiva con retroceso. Comienza con la verificación de la condición de salida row < n, y procede a tomar decisiones de búsqueda en su nivel de recurrencia (es decir, elegir una posible posición para el número de reina row). Después de cada iteración, se realiza una llamada recursiva para construir sobre la configuración que la función ha encontrado hasta ahora; eventualmente, " rowtoca fondo" cuando llega na la llamada recursiva que tiene nniveles profundos.

La estructura general de una función recursiva es algo como esto:

myRecursiveFunction(inputValue)
begin
   if evaluateBaseCaseCondition(inputValue)=true then
       return baseCaseValue;
   else
       /*
       Recursive processing
       */
       recursiveResult = myRecursiveFunction(nextRecursiveValue); //nextRecursiveValue could be as simple as inputValue-1
       return recursiveResult;
   end if
end

El texto que marqué como /*recursive processing*/podría ser cualquier cosa. Se podría incluir un bucle, si el problema está resuelto lo requiere, y también podría incluir llamadas recursivas a myRecursiveFunction.

Seguramente puede usar bucles en una función recursiva. Lo que hace que una función sea recursiva es solo el hecho de que la función se llama a sí misma en algún punto de su ruta de ejecución. Sin embargo, debe tener alguna condición para evitar llamadas de recursión infinitas de las cuales su función no puede regresar.

Las llamadas y bucles recursivos son solo dos formas / construcciones para implementar un cálculo iterativo.

Un whilebucle corresponde a una llamada recursiva de cola (ver, por ejemplo, aquí ), es decir, una iteración en la que no necesita guardar resultados intermedios entre dos iteraciones (todos los resultados de un ciclo están listos cuando ingresa al siguiente ciclo). Si necesita almacenar resultados intermedios que puede usar nuevamente más tarde, puede usar un whilebucle junto con una pila (ver aquí ) o una llamada recursiva no recursiva de cola (es decir, arbitraria).

Muchos idiomas le permiten usar ambos mecanismos y puede elegir el que mejor se adapte a usted e incluso mezclarlos en su código. En lenguajes imperativos como C, C ++, Java, etc., normalmente usa un bucle whileo forcuando no necesita una pila, y usa llamadas recursivas cuando necesita una pila (implícitamente usa la pila de tiempo de ejecución). Haskell (un lenguaje funcional) no ofrece una estructura de control de iteración, por lo que solo puede usar llamadas recursivas para realizar la iteración.

En su ejemplo (vea mis comentarios):

// queens should have type int [] , not int.
private boolean placeQueen(int row, int [] queens, int n)
{
    boolean result = false;
    if (row < n)
    {
        // Iterate with queens[row] = 1 to n - 1.
        // After each iteration, you either have a result
        // in queens, or you have to try the next column for
        // the current row: no intermediate result.
        while ((queens[row] < n - 1) && !result)
        {
            queens[row]++;
            if (verify(row,queens,n))
            {
                // I think you have 'result' here, not 'ok'.
                // This is another loop (iterate on row).
                // The loop is implemented as a recursive call
                // and the previous values of row are stored on
                // the stack so that we can resume with the previous
                // value if the current attempt finds no solution.
                result = placeQueen(row + 1,queens,n);
            }
        }
        if (!result) {
            queens[row] = -1;
        }
    }else{
        result = true;
    }
    return result;
}

Tiene razón al pensar que existe una relación entre recursividad e iteración o bucle. Los algoritmos recursivos a menudo se convierten de forma manual o incluso automática en soluciones iterativas mediante la optimización de llamadas de cola.

En ocho reinas, la parte recursiva está relacionada con el almacenamiento de datos necesarios para el seguimiento posterior. Cuando piensa en la recursividad, es valioso pensar en lo que se empuja en la pila. La pila puede contener parámetros de paso por valor y variables locales que juegan un papel clave en el algoritmo, o, a veces, cosas que aparentemente no son tan relevantes como la dirección de retorno o, en este caso, un valor pasado con el número de reinas que se utiliza pero no modificado por el algoritmo

La acción que ocurre en ocho reinas es que esencialmente se nos da una solución parcial para cierto número de reinas en las primeras columnas a partir de las cuales determinamos iterativamente opciones válidas hasta ahora en la columna actual que pasamos recursivamente para ser evaluadas para el columnas restantes A nivel local, ocho reinas realizan un seguimiento de qué fila está intentando y, si se produce el seguimiento hacia atrás, está listo para avanzar por las filas restantes o para realizar un seguimiento posterior simplemente regresando si no encuentra otra fila que pueda funcionar.

La parte "crear una versión más pequeña del problema" puede tener bucles. Mientras el método se llame a sí mismo pasando como parámetro la versión más pequeña del problema, el método es recursivo. Por supuesto, se debe proporcionar una condición de salida, cuando se resuelve la versión más pequeña posible del problema y el método devuelve un valor, para evitar una condición de desbordamiento de la pila.

El método en su pregunta es recursivo.

La recursión básicamente llama a su función nuevamente y la principal ventaja de la recursión es que ahorra memoria. La recursión puede tener bucles, se utilizan para realizar alguna otra operación.