Recursive functions in Javascript. Good or bad practice?

To say that it is bad practice is an exaggeration but if you can avoid it, the better.

I explain,

The use of recursive functions fills the call stack faster and will most likely throw the Maximum call stack size exceededunchecked error.

Another disadvantage of recursive functions is that they will make the call stack very long, which would make debugging difficult because you would have to search through all the records in which iteration failed, something that does not help much to solve a problem. That is why the use of a recursive function must be limited to recursions that are not very long.

The maximum stack size is browser specific. For example chrome can accept 21k while operating 32k.

To avoid this, there are loops while, forand foreachthey do not save each line of code executed by iteration in the call stack, so they do not have an execution limit since they do not fill the stack and they also make it easy to identify an error since the stack is very small. compared to recursion.

Update 1:

Can I deduce that it is a bad practice?

If you are interested in reducing the size of the stack, you could say yes. If you can avoid recursion, the better.

Is it better to avoid them or do they have a specific use for which they are ideal?

Loops can solve a problem just like recursion and with less cost, so a loop is better than a recursion.

Since setIntervalit is a loop, does it enter the group of while, for, foreach and does not save the stack?

setIntervalis not a loop, but saves the function reference in a task that is executed when the main javascript loop is available and does not add on the stack because the same function reference is used at the end.

TL;DR

It's not bad practice, it's a resource.
The question really should have been whether or not to apply recursion and narrow the context to a specific problem.

A problem is suitable for solving with recursion when it can be modeled as a function that calls itself and with each call gets a little closer to a cutoff condition (where it stops calling itself, to return a result). which is (or is part of) the solution.

Feature Status

In the two cases you are comparing there is a fundamental difference: The state of the function.

In the case of recursion, all variables (state) of the function are preserved when iterating. This way every time a call ends, it goes back one step and the state is automatically restored.

In the case of the loop ( for/ while) the state changes with each iteration, and if you want to preserve the current state (the values ​​of the variables at that moment) to go back (backtracking) in the future, you must use some auxiliary structure such as a vector that acts as a stack, and put there objects with the variables that we need. So we somehow end up doing the same thing as the recursive algorithm but in a more complicated way.

The exposed example is very trivial, but in this case the state comes to be represented by the variable count, and there is not much reason to remember that state for this exercise other than to know when to cut.

To solve other problems like evaluating moves on a chessboard (a bishop that can go both to the right and to the left for example), preserving the state in each loop or iteration is important.

Also to solve logic problems where all the alternatives are tested (finite or up to a level x depth of calls) until finding one that solves the problem (or determining that it has no solution).

While this question is limited to javascript, other languages ​​like Prolog have recursion as a core part of the language.

For this reason, recursion is a resource that is suitable or not suitable for a given problem, and not a good or bad practice in general.

Example (Boatman Problem)

To give an example I will use a known issue:

" A shepherd has to cross a wolf, a goat, and a lettuce plant from one side of a river to the other using a boat / barge where only the shepherd and one of the three elements to cross (wolf, goat, or lettuce) enter. ). The question is that, for obvious reasons, the wolf cannot be alone with the goat, nor the goat with the lettuce. How can the shepherd cross the 3 elements? "

Tip: The shepherd can cross alone in the boat.

To solve this exercise we need:

1) Model the problem state:

It can serve an array of 4 elements (WOLF, GOAT, LETTUCE, SHEPHERD) where each element can be true if it is on the left bank of the river, and false, if it is on the right bank of the river.

2) Determine an initial state, which is this array with all true values ​​(They are all in the left margin).

3) Determine a final state, which is the same array with all false values ​​(All have managed to cross to the right margin).

4) Starting from the initial state, iterate all the possible crossings until reaching the final state (the solution), or until there are no possible crossings left to carry out. The possible crossings are those where the element to be crossed is on the same side as the shepherd, and after crossing no one can eat anyone.

Note: In this problem cycles can occur (wolf and shepherd go back and forth from one side of the river to the other continuously) so you have to have extra control to detect these cycles and break them.

It is important to note that, at least for these solutions, previous states must be "remembered" leading to each new state. This is because after trying all possible junctions from a given state, if none of them reached a solution, then that state must be discarded and the previous state must be tried again.

In the program made with recursion, the state and the path remain in the program's call stack, together with the line that was being executed and the value of the subscript forthat indicates the element that was being crossed.

In the program made with whilethe state, together with the path and the element that was crossing, they are saved in a vector that works as a stack (LIFO) within the same program. The program line is irrelevant in this version since everything is executed in the same loop and the state to be evaluated in each iteration changes, either generating a new one (and storing the current one) or restoring one previously stored in the vector.

The program raised with recursion:

function cruzarElRio(estado,camino){
    logCamino(camino);
    logEstado("cruzando río -> ", estado);

    // Se controla que nadie se coma a nadie
    if(estadoValido(estado) === false){
        console.log("El estado es inválido.");
        return -1;
    }

    //  Que no hayamos caido en este estado anteriormente
    if(cicloDetectado(estado, camino) === true ){
        console.log("El estado ya fue evaluado (ciclo).");
        return -1;
    }

    // agregamos el estado a la copia local del camino.
    camino.push(estado);

    // checkear si este estado es el final
    if(cruzaron(estado) === true){
        console.log("Solución encontrada!!");
        return camino;
    }

    // Probar cruzando de a uno por vez
    for(let i=0; i<4; i++){
        if(puedeCruzar(i, estado)){
            let proxEstado = cruzar(i, estado);     
            let proxCamino = camino.map( (x) => x); // Hace una copia del array.
            let res = cruzarElRio(proxEstado, proxCamino);
            if(res !== -1) return res; 
        }
    }
    console.log("El camino no tiene solución. Se retorna al camino previo.");
    return -1;

}

It for(let i=0; i<4; i++){tries to traverse each element one at a time and for each traverse a new modified state is generated which is used to call the recursive function.

When this happens, the local values ​​before the call (state, path, and the index of the for) are preserved on the call stack without you having to do anything else.

If it turns out that the invocation does not lead to a solution, at some point the function returns to this point, and the values ​​of state, path, and index forare automatically restored, and even the function returns from within the foron the line following the recursive call.

The proposed solution with a loop: (Code can probably be improved a bit)

function cruzarRioConLoops(estado, camino){
    let stack = [];
    let end = false;

    let quienActual = 0;

    while( end === false ){
        logCamino(camino);
        logEstado("cruzando río -> ", estado);

        if(estadoValido(estado) === false || cicloDetectado(estado, camino) === true ){
            console.log("El estado es inválido o existe un ciclo.");
            if(stack.length > 0){
                let stackItem = stack.pop();
                estado = stackItem.estado;
                camino = stackItem.camino;
                quienActual = stackItem.quienActual;
                quienActual++;
                continue;
            }else{
                end = true;
                continue;
            }
        }

        if(cruzaron(estado) === true){
            console.log("Solución encontrada!!");
            camino.push(estado);
            return camino;
        }

        if( quienActual < 4 ){
            if(puedeCruzar(quienActual, estado)){
                let proxEstado = cruzar(quienActual, estado);       
                let proxCamino = camino.map( (x) => x); // Hace una copia del array.
                proxCamino.push(estado);
                let stackItem = {
                    "estado": estado,
                    "camino": camino,
                    "quienActual": quienActual
                }
                stack.push(stackItem);
                estado = proxEstado;
                camino = proxCamino;
                quienActual = 0;
                continue;       
            } else {
                quienActual++;
                continue;
            }
        }else{
            if(stack.length > 0){
                let stackItem = stack.pop();
                estado = stackItem.estado;
                camino = stackItem.camino;
                quienActual = stackItem.quienActual;
                quienActual++;
                continue;
            }else{
                end = true;
                continue;
            }
        }   
    }
}

In this version the whole program runs in a loop. quienActualrepresents the element to cross in the iteration. Those elements enabled to cross will generate new states to test. Unlike the previous version, the current state is replaced on each iteration. Replacement may be due to:

• A crossing that generated a new state. In this case the previous state is saved in the array (stack) by doing a push()before replacement.

• A dead-end path that results in restoring a previous state by doing a pop()and advancing quienActualto attempt the junction with the next item.

The complete code:

/* Verifica que todos estén del otro lado del río.
 */
function cruzaron(estado){
	return estado.orillaIzq[LOBO] === false
	       && estado.orillaIzq[CABRA] === false
	       && estado.orillaIzq[LECHUGA] === false
	       && estado.orillaIzq[PASTOR] === false
}

/*
 El lado actual es donde está el PASTOR que es quien cruza las cosas
 en la barca.
*/
function ladoActual(estado){
	return (estado.orillaIzq[PASTOR] === true) ? "I" : "D";
}

/*
	Solo determina si "quien" está del mismo lado del PASTOR de forma
	de estar habilitado a ser cruzado al otro lado
*/
function puedeCruzar(quien, estado){
	let lado = ladoActual(estado);
	if(lado === "I"){
		if(estado.orillaIzq[quien] === false) return false;	
	}else{
		if(estado.orillaIzq[quien] === true) return false;
	}
	return true;
}

/*
  Verifica que el estado no rompa alguna condición. Que la cabra 
  no se coma la lechuga, y que el lobo no se coma a la cabra.
*/
function estadoValido(estado){
	if( estado.orillaIzq[LOBO] === estado.orillaIzq[CABRA] 
	    && estado.orillaIzq[PASTOR] !== estado.orillaIzq[LOBO] ){
		return false;
	}
	
	if( estado.orillaIzq[CABRA] === estado.orillaIzq[LECHUGA] 
	    && estado.orillaIzq[PASTOR] !== estado.orillaIzq[CABRA] ){
		return false;
	}
	
	return true;
}

/*
 Permite comparar dos estados para saber si son iguales o no.
*/
function eqEstado(e1, e2){
	return e1.orillaIzq[LOBO] === e2.orillaIzq[LOBO]
	       && e1.orillaIzq[CABRA] === e2.orillaIzq[CABRA]
		   && e1.orillaIzq[LECHUGA] === e2.orillaIzq[LECHUGA]
		   && e1.orillaIzq[PASTOR] === e2.orillaIzq[PASTOR];
}

/*
  Este problema permite que pueda entrarse en un ciclo (que el lobo no dede de ir y venir de
  un lado al otro por ejemplo). Al buscar el estado nuevo en el "historial" del camino, podemos
  detectar esto y romper el ciclo.
*/
function cicloDetectado(proxEstado, camino){
	for(let i=0; i<camino.length; i++){
		if(eqEstado(camino[i], proxEstado)){
			return true;
		}
	}
	return false;
}

/*
 Mueve a "quien" junto con el pastor al otro lado del río.
 Devuelve un nuevo estado (no altera el pasado por parámetro)
*/
function cruzar(quien, estado){
	let nuevaOrillaIzq = estado.orillaIzq.map( (x) => x );
	let nuevoEstado = {"orillaIzq": nuevaOrillaIzq};
	if( quien !== PASTOR ){
		nuevoEstado.orillaIzq[quien] = !nuevoEstado.orillaIzq[quien];
	}
	nuevoEstado.orillaIzq[PASTOR] = !nuevoEstado.orillaIzq[PASTOR];
	return nuevoEstado;
}

/*
 Muestra el Estado en la consola.
*/
function logEstado(msg, estado){
	let iz = "";
	let da = "";
	let quien = [" LOBO ", " CABRA ", " LECHUGA ", " PASTOR "];
	for(let i=0; i<4; i++){
		if(estado.orillaIzq[i] === true){
			iz += quien[i];
		}else{
			da += quien[i];
		}
	}
	console.log("Estado: " + msg + " " + iz + "/~~~/" + da);
}

/*
 Muestra un camino (lista de estados) en la consola
*/
function logCamino(camino){
	console.log("Camino:");
	for(let i=0; i<camino.length; i++){
		logEstado(""+i, camino[i]);
	}
}


function cruzarRioConLoops(estado, camino){
	let stack = [];
	let end = false;
	
	let quienActual = 0;
	
	while( end === false ){
		logCamino(camino);
		logEstado("cruzando río -> ", estado);
		
		if(estadoValido(estado) === false || cicloDetectado(estado, camino) === true ){
			console.log("El estado es inválido o existe un ciclo.");
			if(stack.length > 0){
				let stackItem = stack.pop();
				estado = stackItem.estado;
				camino = stackItem.camino;
				quienActual = stackItem.quienActual;
				quienActual++;
				continue;
			}else{
				end = true;
				continue;
			}
		}
		
		if(cruzaron(estado) === true){
			console.log("Solución encontrada!!");
			camino.push(estado);
			return camino;
		}
		
		if( quienActual < 4 ){
			if(puedeCruzar(quienActual, estado)){
				let proxEstado = cruzar(quienActual, estado);		
				let proxCamino = camino.map( (x) => x); // Hace una copia del array.
				proxCamino.push(estado);
				let stackItem = {
					"estado": estado,
					"camino": camino,
					"quienActual": quienActual
				}
				stack.push(stackItem);
				estado = proxEstado;
				camino = proxCamino;
				quienActual = 0;
				continue;		
			} else {
				quienActual++;
				continue;
			}
		}else{
			if(stack.length > 0){
				let stackItem = stack.pop();
				estado = stackItem.estado;
				camino = stackItem.camino;
				quienActual = stackItem.quienActual;
				quienActual++;
				continue;
			}else{
				end = true;
				continue;
			}
		}	
	}
}

/**
 La función recursiva. 
 Si el estado es inválido o si presenta ciclos, se retorna y retoma el camino anterior.
 De otro modo, se verifica si llegamos al estado final donde todos cruzaron al otro lado.
 Si todos cruzaron se devuelve el camino que nos llevó hasta acá.
 Si no se llegó se generan nuevos estados para cada uno de los posibles "quien" que pueden cruzar el río.
 Y se llama a la función recursiva con el nuevo estado y con una copia del camino que será la copia local de 
 nueva iteración. 
 La función invocada puede devolver -1 si no se llegó a un resultado, o un array con el camino que llevó a la 
 solución.
*/
function cruzarElRio(estado,camino){
	logCamino(camino);
	logEstado("cruzando río -> ", estado);
	
	if(estadoValido(estado) === false){
		console.log("El estado es inválido.");
		return -1;
	}
	
	if(cicloDetectado(estado, camino) === true ){
		console.log("El estado ya fue evaluado (ciclo).");
		return -1;
	}
	
	camino.push(estado);
	
	if(cruzaron(estado) === true){
		console.log("Solución encontrada!!");
		return camino;
	}
	
	for(let i=0; i<4; i++){
		if(puedeCruzar(i, estado)){
			let proxEstado = cruzar(i, estado);		
			let proxCamino = camino.map( (x) => x); // Hace una copia del array.
			let res = cruzarElRio(proxEstado, proxCamino);
			if(res !== -1) return res; 
		}
	}
	console.log("El camino no tiene solución. Se retorna al camino previo.");
	return -1;

}

let LOBO = 0, CABRA = 1, LECHUGA = 2, PASTOR = 3;

function recursivo(){
  let camino = [];

  let estado = {
    "orillaIzq" : [true, true, true, true],
  }
  
  let res = cruzarElRio(estado, camino);
  if(res === -1) {
    console.log("sin solución");
  } else {
    logCamino(res);
  }
}

function conWhile(){

  let camino = [];

  let estado = {
    "orillaIzq" : [true, true, true, true],
  }
  
  let res = cruzarRioConLoops(estado, camino);
  if(res === -1) {
    console.log("sin solución");
  } else {
    logCamino(res);
  }
}

button{
width: 200px;
margin: 10px;
}

<p>Como cruzar un lobo, una cabra, y una lechuga de un lado al otro del río sin que la cabra se quede sola con el lobo, ni que la lechuga se quede sola con la cabra y utilizando un bote/barcaza con dos lugares.</p>
<p>Resultado en log de la consola</p>
<button onclick="recursivo()">Recursivo</button><br>
<button onclick="conWhile()">Con While</button>