Recursividad
Introducido| English | Significado |
|---|---|
| recursive/rɪˈkɜːsɪv/ | Recursivo |
| base case/beɪs keɪs/ | Caso base |
| recursive case/rɪˈkɜːsɪv keɪs/ | Caso recursivo |
| call stack/kɔːl stæk/ | Pila de llamadas |
| stack frame/stæk freɪm/ | Marco de pila |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | Desbordamiento de pila |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | Memización |
Una definición que se contiene a sí misma
- ¿Cómo defines qué es un ancestro? Tu padre es un ancestro. Y el ancestro de tu padre también lo es. Esas dos oraciones definen una cadena ilimitada, y la segunda utiliza la palabra que está definiendo.
- No se trata de un argumento circular, porque la primera oración establece un punto de parada para la cadena. Sin ella, la definición se desplegaría infinitamente.
- Los programas pueden escribirse de esta manera, y para problemas con esa estructura en forma de cadena, una solución recursiva es dramáticamente más corta que un bucle.
- Esta lección cubre el caso base, el caso recursivo, cómo se traza una llamada recursiva y qué hace realmente la pila de llamadas debajo.
Los dos casos
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
- El caso base es una versión del problema lo suficientemente pequeña como para responder directamente, sin necesidad de otra llamada. Es lo que detiene la recursión.
- El caso recursivo vuelve a llamar a la función con una entrada más pequeña, acercándose al caso base.
- Ambos son necesarios. Una recursión sin caso base nunca se detiene; una cuya entrada no se reduce nunca alcanza el caso base.
Every recursive algorithm must have a base case because:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
The base case is the condition that ends the chain of calls; without it the recursion runs forever.
Recursion is a natural fit for self-similar problems (trees, divide-and-conquer), but each call adds a stack frame — so without a base case it overflows the stack.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
A simple counting loop is cleaner for plain iteration; recursion shines when the problem contains smaller copies of itself.
What must a recursive routine have to terminate? Select todos that apply.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
A base case alone is not enough: if the input never shrinks, the base case is never reached and frames pile up until the stack overflows.
Ejemplo resuelto: trazar una recursión
- Trazar
Factorial(4). - Subida (winding up):
Factorial(4)necesita4 * Factorial(3), que necesita3 * Factorial(2), que necesita2 * Factorial(1). Aún no se ha realizado ninguna multiplicación; cada llamada está esperando. - Caso base:
Factorial(1)retorna 1 sin hacer ninguna llamada. - Descenso (unwinding): Se retorna
2 * 1 = 2, luego3 * 2 = 6, luego4 * 6 = 24. - Muestra ambas direcciones. Un trazado que solo baja o solo sube pierde la mitad de los puntos.
Recursion unwinds from the leaves up
Step through fib(4) in the order the calls actually finish: the leaves (base cases) resolve first, then each parent combines its children. Notice fib(2) is computed twice — that repeated work is why naive recursion is slow.
What does Factorial(4) return?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
4 × 3 × 2 × 1 = 24.
Lo que hace la máquina
- Cada llamada necesita su propia copia de sus parámetros y variables locales, porque
Factorial(3)yFactorial(2)son llamadas diferentes con distintos valores den. - Esas copias viven en un marco de pila sobre la pila de llamadas: un marco por llamada en curso, que guarda los parámetros, las variables locales y la dirección de retorno.
- Un marco es empujado en cada llamada y eliminado cuando retorna. Por eso los valores regresan en orden inverso al de las llamadas: la pila de llamadas es una pila, exactamente como el ADT del tema 10.
Put the events of evaluating Factorial(4) in order.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Nothing is multiplied on the way down; every call waits. The multiplications all happen as the stack unwinds.
Qué puede salir mal
- No hay caso base, o un caso base que nunca se alcanza: la recursión nunca se detiene, los marcos se apilan y la pila de llamadas se queda sin memoria. Eso es un desbordamiento de pila.
- Recursión profunda: incluso una recursión correcta de un millón de niveles necesita un millón de marcos, por lo que puede agotar la memoria donde un bucle no usaría nada.
- Trabajo repetido: la Fibonacci recursiva ingenua recalcula los mismos valores exponencialmente muchas veces. Solúcionalo con un bucle o con memorización, almacenando cada resultado la primera vez que se calcula.
Match each recursion term to what it means.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
A recursion needs a base case to stop and a recursive case to shrink the problem; each call adds a stack frame.
A stack frame for a function call holds:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Each frame stores that call's parameters, locals and where to resume — so calls don't trample each other.
Each call in progress keeps its parameters and locals in its own ____ on the call stack.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Pushed on call, popped on return. That is why values come back in the reverse of the order the calls were made.
Recursión o iteración
- La recursión se adapta a problemas autosimilares, donde el problema contiene una copia más pequeña de sí mismo: recorrido de árboles, divide y vencerás como la búsqueda binaria y el ordenamiento por fusión, y la cadena de ancestros anterior.
- La iteración se adapta a todo lo demás, y no utiliza memoria adicional para la repetición.
- Cualquier cosa recursiva puede escribirse de forma iterativa y viceversa. La elección depende de cuál exprese el problema con claridad, ponderado contra la memoria que cuesta la pila.
A recursive routine crashes with a stack overflow. Which explanation is correct?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Stack overflow is about frames, not arithmetic. A number too large for its register is an arithmetic overflow, a different thing entirely.
Ejemplo resuelto: plantear los riesgos
- Un estudiante escribe una rutina recursiva y esta falla con un desbordamiento de pila. Da dos causas posibles.
- No hay caso base, o el caso base nunca puede alcanzarse porque la entrada no se hace más pequeña en cada llamada, por lo que las llamadas continúan indefinidamente y los marcos se acumulan.
- La recursión es correcta pero demasiado profunda: cada una de las muchas llamadas conserva su propio marco de pila, y la pila de llamadas se queda sin memoria antes de alcanzar el caso base.
- Ambas causas se refieren a la acumulación de marcos. Di qué se acumula y por qué nunca se detiene.
Puntos que se pierden
- Una recursión necesita ambas cosas: un caso base y una entrada que se haga más pequeña. Nombrar solo el caso base es cumplir la mitad de la condición.
- En un trazado, muestra las llamadas subiendo y los valores descendiendo. Ambas direcciones otorgan puntos.
- Cada llamada tiene sus propios parámetros y variables locales, en su propio marco de pila. Por eso la recursión consume memoria que la iteración no usa.
- Un desbordamiento de pila es quedarse sin memoria de pila por haber demasiados marcos, no un desbordamiento aritmético.
Ya lo tienes
- Una rutina recursiva necesita un caso base resuelto directamente y un caso recursivo que se llame a sí mismo con una entrada más pequeña.
- Trazala en ambas direcciones: llamadas subiendo hasta el caso base, luego valores descendiendo de vuelta.
- Cada llamada tiene su propio marco de pila sobre la pila de llamadas, empujado en la llamada y eliminado al retornar, lo cual explica por qué la recursión consume memoria.
- Riesgos: la ausencia de un caso base alcanzable provoca recursión infinita y desbordamiento de pila; la recursión profunda agota la memoria; y el trabajo repetido requiere un bucle o memorización.