Recursion · Recursión
| English | Español |
|---|---|
| Recursion/rɪˈkɜːʃn/ | Recursividad |
| base case/beɪs keɪs/ | caso base |
| recursive case/rɪˈkɜːsɪv keɪs/ | caso recursivo |
| unwind/ʌnˈwaɪnd/ | desenrollar |
A method that calls itself
- Recursion 递归 is when a method calls itself to solve a smaller version of the same problem.
- Every recursion needs two parts: a base case 基准情形 and a recursive case 递归情形.
- The base case stops the recursion — a small input the method answers directly.
- The recursive case calls the method again on a smaller input.
Un método que se llama a sí mismo
- Recursividad 递归 es cuando un método se llama a sí mismo para resolver una versión más pequeña del mismo problema.
- Toda recursividad necesita dos partes: un caso base 基准情形 y un caso recursivo 递归情形.
- El caso base detiene la recursividad — una entrada pequeña que el método responde directamente.
- El caso recursivo vuelve a llamar al método con una entrada más pequeña.
The base case
- Without a base case, a method calls itself forever — a
StackOverflowError. - The base case handles the smallest input without another call.
- Example:
factorial(0)returns1directly — no more calls. - Always check: does every path eventually reach the base case?
El caso base
- Sin un caso base, un método se llama a sí mismo infinitamente — provocando un
StackOverflowError. - El caso base maneja la entrada más pequeña sin otra llamada.
- Ejemplo:
factorial(0)devuelve1directamente — no hay más llamadas. - Verifica siempre: ¿cada camino termina alcanzando el caso base?
The recursive case
- The recursive case does a little work, then calls itself on a smaller input.
factorial(n)returnsn * factorial(n - 1)— the input shrinks by one each call.- Each call waits for the smaller call to return before finishing.
- The calls stack up, hit the base case, then unwind 回退 back to the top.
El caso recursivo
- El caso recursivo realiza un poco de trabajo y luego se llama a sí mismo con una entrada más pequeña.
factorial(n)devuelven * factorial(n - 1)— la entrada se reduce en uno en cada llamada.- Cada llamada espera a que la llamada más pequeña devuelva antes de terminar.
- Las llamadas se apilan, alcanzan el caso base y luego se desapilan 回退 hacia arriba.
How the calls stack
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)returns1; then the stack unwinds:1, 1, 2, 6.- Each call keeps its own copy of the parameters until it returns.
- Tracing a recursion means following the calls down, then the returns up.
Cómo se apilan las llamadas
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)devuelve1; luego la pila se desenrolla:1, 1, 2, 6.- Cada llamada conserva su propia copia de los parámetros hasta que retorna.
- Rastrear una recursividad significa seguir las llamadas hacia abajo y los retornos hacia arriba.
Every recursion needs a base case that stops it — and each recursive call must move TOWARD that base case (a smaller input). Miss the base case, or call on the same or a larger input, and the method recurses forever until a StackOverflowError. Trace by following calls down to the base case, then the returns back up.
Toda recursividad necesita un caso base que la detenga — y cada llamada recursiva debe aproximarse A ESE caso base (con una entrada más pequeña). Si omites el caso base o llamas con la misma o una entrada mayor, el método recursionará infinitamente hasta generar un StackOverflowError. Para rastrearlo, sigue las llamadas hacia abajo hasta el caso base y luego los retornos hacia arriba.
sum(n) = 1 + 2 + … + n by recursion:
- Base case:
if (n == 0) return 0; - Recursive case:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
sum(n) = 1 + 2 + … + n por recursividad:
- Caso base:
if (n == 0) return 0; - Caso recursivo:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
Recursion is a method calling itself on a smaller input. It needs a base case (stops directly, no more calls) and a recursive case (does a little work, then recurses on a smaller input). Calls stack down to the base case, then unwind back up. Miss the base case and you get a StackOverflowError.
Recursividad es un método que se llama a sí mismo con una entrada más pequeña. Requiere un caso base (detiene directamente, sin más llamadas) y un caso recursivo (realiza un poco de trabajo y luego recursiona con una entrada más pequeña). Las llamadas se apilan hacia abajo hasta el caso base y luego se desapilan hacia arriba. Si falta el caso base, obtendrás un StackOverflowError.
factorial(3) unwinds from the base case up · factorial(3) se desenrolla desde el caso base hacia arriba
fact(0) returns 1 (base case); each parent multiplies: 1, 1, 2, 6. · fact(0) devuelve 1 (caso base); cada padre multiplica: 1, 1, 2, 6.
A recursive method is one that... · Un método recursivo es aquel que...
Recursion = a method calling itself. · Recursión = un método que se llama a sí mismo.
The base case is... · El caso base es...
The base case stops the recursion. · El caso base detiene la recursión.
A recursion with no reachable base case causes... · Una recursión sin caso base alcanzable causa...
It recurses forever until the stack overflows. · Recurciona infinitamente hasta que la pila se desborda.
The recursive case must call itself on... · El caso recursivo debe llamarse a sí mismo con...
Each call must shrink toward the base case. · Cada llamada debe reducirse hacia el caso base.
If factorial(0)=1 and factorial(n)=nfactorial(n-1), what is factorial(3)? · Si factorial(0)=1 y factorial(n)=nfactorial(n-1), ¿cuál es factorial(3)?
3 * 2 * 1 * 1 = 6.
Each recursive call keeps its own copy of its parameters until it returns. · Cada llamada recursiva mantiene su propia copia de sus parámetros hasta que retorna.
Calls stack independently, then unwind. · Las llamadas apilan independientemente, luego se desenrollan.