Home / Questions / 278219
Accepted
x3k
Asked: 2020-07-12 00:10:38 +0800 CST 2020-07-12 00:10:38 +0800 CST

Javascript 中的递归函数。好的还是坏的做法？

  • 772

我一直以不好的眼光看待递归函数，我拒绝了它们，转而支持其他选择。

我为什么要这样做？：

foo(0);
function foo(cont){
  console.log(cont);
  cont++;
  if(cont<50){
    foo(cont);
  }
}

能够做到这一点：

foo();
function foo(){
  for(let cont=0;cont<50;cont++){
    console.log(cont);
  }
}

查了资料，发现可以使用递归函数来优化Tail Call Optimization 递归函数式javascript

如果在前面的片段中我们模拟一个更大的循环，我觉得没有多大意义，例如：cont < 99999. 当他完成它时，它función recursiva在到达终点之前失败了。for

另一方面，如果我们模拟一个无限循环，for则不会这样做，而función recursiva确实会尝试并再次给出错误。

javascript

2 Answers

  1. 说这是不好的做法是夸大其词，但如果你能避免它，那就更好了。

    我解释，

    使用递归函数可以更快地填充调用堆栈，并且很可能会抛出Maximum call stack size exceeded未经检查的错误。

    递归函数的另一个缺点是它们会使调用堆栈非常长，这会使调试变得困难，因为您必须搜索所有迭代失败的记录，这对解决问题没有多大帮助。这就是为什么递归函数的使用必须限于不是很长的递归。

    最大堆栈大小是特定于浏览器的。例如 chrome 在运行 32k 时可以接受 21k。

    为了避免这种情况，有循环while，for并且foreach它们不会将迭代执行的每一行代码保存在调用堆栈中，因此它们没有执行限制，因为它们不会填充堆栈，并且它们也很容易识别错误因为堆栈非常小。与递归相比。

    更新1：

    我可以推断这是一种不好的做法吗？

    如果你有兴趣减少堆栈的大小，你可以说是。如果可以避免递归，那就更好了。

    是避免使用它们更好，还是它们有理想的特定用途？

    循环可以像递归一样解决问题，而且成本更低，因此循环比递归更好。

    既然setInterval是循环，是不是进入了 , , 的组，while不 存栈呢？forforeach

    setInterval不是循环，而是将函数引用保存在一个任务中，该任务在主 javascript 循环可用时执行并且不会添加到堆栈上，因为最后使用了相同的函数引用。

    • 19
  2. Best Answer

    TL;博士

    这不是坏习惯，它是一种资源。
    问题真的应该是是否应用递归并将上下文缩小到特定问题。

    当一个问题可以被建模为一个调用自身的函数并且每次调用都更接近于一个截止条件（它停止调用自身，返回一个结果）时，一个问题适合用递归解决。的）解决方案。

    功能状态

    在您比较的两种情况下，有一个根本区别：函数的状态。

    在递归的情况下，函数的所有变量（状态）在迭代时都会被保留。这样每次通话结束时，它会返回一个步骤，并自动恢复状态。

    在循环（for/ while）的情况下，状态随着每次迭代而变化，并且如果您想保留当前状态（当时变量的值）以供将来返回（回溯），则必须使用一些辅助结构，例如充当堆栈的向量，并在其中放置带有我们需要的变量的对象。所以我们以某种方式最终以一种更复杂的方式做与递归算法相同的事情。

    公开的示例非常简单，但在这种情况下，状态由变量 表示，count除了知道何时剪切之外，没有太多理由在本练习中记住该状态。

    要解决其他问题，例如评估棋盘上的移动（例如，可以左右移动的象），保留每个循环或迭代中的状态很重要。

    还解决逻辑问题，其中测试了所有替代方案（有限或高达 x 级别的调用深度），直到找到一个解决问题的方案（或确定它没有解决方案）。

    虽然这个问题仅限于 javascript，但其他语言如 Prolog 都将递归作为语言的核心部分。

    出于这个原因，递归是适合或不适合给定问题的资源，而不是一般的好或坏实践。

    示例（船夫问题）

    举个例子，我将使用一个已知问题：

    "牧羊人必须使用船/驳船从河流的一侧穿过狼、山羊和莴苣植物到另一侧，只有牧羊人和三个要素之一（狼、山羊或莴苣）才能穿过进入。）。问题是，出于显而易见的原因，狼不能与山羊单独相处，山羊与生菜也不能单独相处。牧羊人如何跨越三个元素？

    提示：牧羊人可以单独在船上过河。

    为了解决这个练习，我们需要：

    1）对问题状态建模：

    它可以为一个包含 4 个元素（WOLF、GOAT、LETTUCE、SHEPHERD）的数组提供服务，其中每个元素在河的左岸可以为真，如果在河的右岸则为假。

    2）确定一个初始状态，也就是这个数组中所有的真值（都在左边距）。

    3) 确定一个最终状态，也就是所有假值的同一个数组（都已成功越过右边距）。

    4）从初始状态开始，迭代所有可能的交叉点，直到达到最终状态（解决方案），或者直到没有可能的交叉点可以执行。可能的穿越是那些要穿越的元素与牧羊人在同一侧，穿越后任何人都不能吃任何人的穿越。

    注意：在这个问题中可能会出现循环（狼和牧羊人不断地从河流的一侧到另一侧来回走动），因此您必须有额外的控制来检测这些循环并打破它们。

    重要的是要注意，至少对于这些解决方案，必须“记住”以前的状态，从而导致每个新状态。这是因为在尝试了给定状态的所有可能结点之后，如果它们都没有达到解决方案，则必须丢弃该状态，并且必须再次尝试先前的状态。

    在使用递归创建的程序中，状态和路径与正在执行的行和for指示被越过的元素的下标值一起保留在程序的调用堆栈中。

    在使用while状态创建的程序中，与路径和正在交叉的元素一起，它们被保存在一个向量中，该向量在同一程序中作为堆栈 (LIFO) 工作。程序行在此版本中无关紧要，因为所有内容都在同一个循环中执行，并且每次迭代中要评估的状态都会发生变化，要么生成新状态（并存储当前状态），要么恢复先前存储在向量中的状态。

    递归提出的程序：

    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;

}

    它for(let i=0; i<4; i++){尝试一次遍历每个元素，并且每次遍历都会生成一个新的修改状态，该状态用于调用递归函数。

    发生这种情况时，调用之前的本地值（状态、路径和 的索引for）会保留在调用堆栈上，而您无需执行任何其他操作。

    如果事实证明调用没有导致解决方案，则函数在某个时刻返回到该点，并且状态、路径和索引的值for会自动恢复，甚至函数从foron the内部返回递归调用之后的行。

    建议的带有循环的解决方案：（ 代码可能会有所改进）

    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;
            }
        }   
    }
}

    在这个版本中，整个程序循环运行。 quienActual表示要在迭代中交叉的元素。那些能够交叉的元素将生成新的状态进行测试。与以前的版本不同，每次迭代都会替换当前状态。更换可能是由于：

    • 产生新状态的交叉口。push()在这种情况下，前一个状态通过替换前保存在数组（堆栈）中。

    • 一条死路，通过执行 apop()并推进quienActual以尝试与下一个项目连接来恢复先前的状态。

    完整代码：

    /* 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>

    • 14