Recursion · Recursión
| English | Español |
|---|---|
| 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/ | memorización |
A definition that contains itself
- How do you say what an ancestor is? Your parent is an ancestor. So is your parent's ancestor. Those two sentences define an unbounded chain, and the second one uses the word it is defining.
- That is not a circular argument, because the first sentence gives the chain somewhere to stop. Without it, the definition would unwind for ever.
- Programs can be written the same way, and for problems shaped like that chain, a recursive 递归 solution is dramatically shorter than a loop.
- This lesson is the base case 基本情形 and the recursive case 递归情形, how a recursive call is traced, and what the call stack 调用栈 is doing underneath.
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.
The two cases
- The base case is a version of the problem small enough to answer directly, with no further call. It is what stops the recursion.
- The recursive case calls the function again with a smaller input, moving towards the base case.
- Both are required. A recursion with no base case never stops; one whose input does not shrink never reaches the base case.
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: · Todo algoritmo recursivo debe tener un caso base porque:
The base case is the condition that ends the chain of calls; without it the recursion runs forever. · El caso base es la condición que termina la cadena de llamadas; sin él la recursión corre para siempre.
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. · La recursión es una opción natural para problemas autosimilares (árboles, divide y vencerás), pero cada llamada añade un marco de pila — así que sin un caso base se desborda la pila.
A simple counting loop is cleaner for plain iteration; recursion shines when the problem contains smaller copies of itself. · Un bucle de conteo simple es más limpio para iteración básica; la recursión destaca cuando el problema contiene copias más pequeñas de sí mismo.
What must a recursive routine have to terminate? Select all · todos that apply. · ¿Qué debe tener una rutina recursiva para terminar? Selecciona todos los que correspondan.
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. · Un caso base solo no es suficiente: si la entrada nunca se reduce, el caso base nunca se alcanza y los marcos se acumulan hasta que la pila se desborda.
Worked example: trace a recursion
- Trace
Factorial(4). - Winding up:
Factorial(4)needs4 * Factorial(3), which needs3 * Factorial(2), which needs2 * Factorial(1). Nothing has been multiplied yet; each call is waiting. - Base case:
Factorial(1)returns 1 without calling anything. - Unwinding:
2 * 1 = 2is returned, then3 * 2 = 6, then4 * 6 = 24. - Show both directions. A trace that only goes down, or only comes back, loses half the marks.
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 · La recursión se desenrolla desde las hojas hacia arriba
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. · Paso a paso fib(4) en el orden en que realmente terminan las llamadas: las hojas (casos base) se resuelven primero, luego cada padre combina sus hijos. Observa que fib(2) se calcula dos veces — ese trabajo repetido es por qué la recursión ingenua es lenta.
What does Factorial(4) return? · ¿Qué devuelve Factorial(4)?
4 × 3 × 2 × 1 = 24.
What the machine is doing
- Every call needs its own copy of its parameters and local variables, because
Factorial(3)andFactorial(2)are different calls with different values ofn. - Those copies live in a stack frame 栈帧 on the call stack: one frame per call in progress, holding the parameters, the locals and the return address.
- A frame is pushed on each call and popped when it returns. That is why the values come back in the reverse of the order they were called: the call stack is a stack, exactly the ADT from topic 10.
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. · Coloca los eventos de evaluar Factorial(4) en orden.
Nothing is multiplied on the way down; every call waits. The multiplications all happen as the stack unwinds. · Nada se multiplica en el camino descendente; todas las llamadas esperan. Las multiplicaciones ocurren todas mientras la pila se desenrolla.
What goes wrong
- No base case, or a base case that is never reached: the recursion never stops, frames pile up, and the call stack runs out of memory. That is a stack overflow 栈溢出.
- Deep recursion: even a correct recursion of a million levels needs a million frames, so it can exhaust memory where a loop would use none.
- Repeated work: naive recursive Fibonacci recomputes the same values exponentially many times. Fix it with a loop, or with memoisation 记忆化, storing each result the first time it is computed.
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. · Empareja cada término de recursión con lo que significa.
A recursion needs a base case to stop and a recursive case to shrink the problem; each call adds a stack frame. · Una recursión necesita un caso base para detenerse y un caso recursivo para reducir el problema; cada llamada añade un marco de pila.
A stack frame for a function call holds: · Un marco de pila para una llamada a función almacena:
Each frame stores that call's parameters, locals and where to resume — so calls don't trample each other. · Cada marco guarda los parámetros, las variables locales y dónde reanudar de esa llamada — para que las llamadas no interfieran entre sí.
Each call in progress keeps its parameters and locals in its own ____ on the call stack. · Cada llamada en curso mantiene sus parámetros y variables locales en su propio ____ en la pila de llamadas.
Pushed on call, popped on return. That is why values come back in the reverse of the order the calls were made. · Se empuja en la llamada, se desecha en el retorno. Por eso los valores vuelven en orden inverso al de las llamadas realizadas.
Recursion or iteration
- Recursion suits self-similar problems, where the problem contains a smaller copy of itself: tree traversal, divide and conquer such as binary search and merge sort, and the ancestor chain above.
- Iteration suits everything else, and uses no extra memory for the repetition.
- Anything recursive can be written iteratively and the reverse is also true. The choice is about which one expresses the problem clearly, weighed against the memory the stack costs.
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? · Una rutina recursiva falla con un desbordamiento de pila. ¿Cuál explicación es correcta?
Stack overflow is about frames, not arithmetic. A number too large for its register is an arithmetic overflow, a different thing entirely. · El desbordamiento de pila trata sobre marcos, no aritmética. Un número demasiado grande para su registro es un desbordamiento aritmético, algo completamente distinto.
Worked example: state the risks
- A student writes a recursive routine and it crashes with a stack overflow. Give two possible causes.
- There is no base case, or the base case can never be reached because the input does not get smaller on each call, so calls continue for ever and frames accumulate.
- The recursion is correct but too deep: each of the very many calls keeps its own stack frame, and the call stack runs out of memory before the base case is reached.
- Both causes are about frames accumulating. Say what accumulates and why it never stops.
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.
Marks that slip away
- A recursion needs both a base case and an input that gets smaller. Naming only the base case is half the condition.
- In a trace, show the calls winding up and the values unwinding. Both directions carry marks.
- Each call has its own parameters and locals, in its own stack frame. That is why recursion costs memory that iteration does not.
- Stack overflow is running out of stack memory from too many frames, not an arithmetic overflow.
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.
You've got it
- a recursive routine needs a base case solved directly and a recursive case that calls itself with a smaller input
- trace it in both directions: calls winding up to the base case, then values unwinding back
- each call has its own stack frame on the call stack, pushed on call and popped on return, which is why recursion costs memory
- risks: no reachable base case gives infinite recursion and stack overflow, deep recursion exhausts memory, and repeated work needs a loop or memoisation
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.