Recursion: base case and recursive case · Recursión: caso base y caso recursivo
A function that calls itself
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- It needs two parts: a base case that stops, and a recursive case that shrinks the problem.
- Without a base case, it would call itself forever and crash.
Una función que se llama a sí misma
- La recursión es cuando una función se llama a sí misma para resolver una versión más pequeña del mismo problema.
- Necesita dos partes: un caso base que detenga la ejecución, y un caso recursivo que reduzca el problema.
- Sin un caso base, se llamaría a sí misma infinitamente y provocaría un fallo.
The base case
- The base case is the smallest problem you can answer directly, with no more calls.
- For factorial,
0!and1!are both1— that is the base case. - Always handle the base case first, so the recursion has somewhere to stop.
El caso base
- El caso base es el problema más pequeño que puedes responder directamente, sin realizar más llamadas.
- Para el factorial, tanto
0!como1!son1; ese es el caso base. - Maneja siempre el caso base primero, para que la recursión tenga un punto de parada.
The recursive case
- The recursive case solves the problem using the answer to a smaller one.
n! = n × (n - 1)!, sofactorial(n)returnsn * factorial(n - 1).- Each call must move closer to the base case, or it will never stop.
El caso recursivo
- El caso recursivo resuelve el problema utilizando la respuesta de uno más pequeño.
n! = n × (n - 1)!, por lo tantofactorial(n)devuelven * factorial(n - 1).- Cada llamada debe acercarse al caso base, de lo contrario nunca se detendrá.
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main(void) {
printf("%d\n", factorial(5)); // 120
return 0;
}
Recursion over an array
- You can recurse along an array by passing an index that moves forward each call.
- The base case is "the index has reached the end" (return
0for a sum). - The recursive case is
a[i] + sum(a, i + 1, n)— this item plus the sum of the rest.
Recursión sobre un array
- Puedes aplicar recursión a un array pasando un índice que avance en cada llamada.
- El caso base es "el índice ha alcanzado el final" (devuelve
0para una suma). - El caso recursivo es
a[i] + sum(a, i + 1, n)— este elemento más la suma del resto.
Common mistakes
- Recursion needs a base case, or the call stack overflows.
- Each call must move closer to the base case.
Errores comunes
- La recursión necesita un caso base, de lo contrario se desbordará la pila de llamadas.
- Cada llamada debe acercarse al caso base.
Now you try
- Write the base case first, then the recursive case that calls itself on a smaller input.
- Keep test values small so the numbers stay inside an
int. - Do not write a
main— the checker provides one.
Ahora tú intentas
- Escribe primero el caso base, luego el caso recursivo que se llame a sí mismo con una entrada más pequeña.
- Mantén los valores de prueba pequeños para que los números permanezcan dentro de un
int. - No escribas un
main— el validador proporciona uno.
Recursion returns up · La recursión retorna hacia arriba
Calls split to a base case, then values return up. · Las llamadas se dividen hasta un caso base, luego los valores retornan hacia arriba.
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do not · no write a main. · Complete int factorial(int n) usando recursión: retorne 1 para n <= 1 (el caso base), de lo contrario n * factorial(n - 1). No escriba una función main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 is 1, otherwise base * power(base, exp - 1). Do not · no write a main. · Complete int power(int base, int exp) usando recursión (asuma que exp >= 0): base elevado a la potencia 0 es 1, de lo contrario base * power(base, exp - 1). No escriba una función main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Complete int array_sum(const int a[], int i, int n) using recursion: it returns the sum of a[i] up to a[n-1]. Base case: i >= n returns · retornos 0. Do not · no write a main. · Complete int array_sum(const int a[], int i, int n) usando recursión: retorna la suma de a[i] hasta a[n-1]. Caso base: si i >= n retorna 0. No escriba una función main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.