Recursión en C#

Problema

¿Cuántas formas de ordenarlos hay?

En la estantería hay 5 libros. ¿De cuántas formas puedes ordenarlos? Para el primer lugar hay 5 opciones, para el segundo 4, después 3, 2 y 1: 5 · 4 · 3 · 2 · 1 = 120. Esto es un factorial, y se escribe 5!.

Con un bucle ya sabes hacerlo:

static int FactorialLoop(int n)
{
    int result = 1;
    for (int i = 2; i <= n; i++)
    {
        result *= i;
    }
    return result;
}

Console.WriteLine(FactorialLoop(5));

Míralo también así: 5! = 5 · 4!. Y 4! = 4 · 3!. La tarea se resuelve mediante la misma tarea, solo que más pequeña. ¿Puede el método decir justo eso?

La idea

Un método que se llama a sí mismo

Puede. Un método que se llama a sí mismo se llama recursivo, y el enfoque es la recursión.

static int Factorial(int n)
{
    if (n == 1)
    {
        return 1;
    }
    return n * Factorial(n - 1);
}

Console.WriteLine(Factorial(5));

Dos cosas hacen que funcione:

Un caso base. Un caso que se resuelve directamente, sin una llamada nueva. Aquí: 1! = 1.
Una tarea más pequeña. Cada llamada se llama a sí misma con un número más cerca del caso base: n - 1.

Míralo

La pila de llamadas

static int Factorial(int n)
{
    if (n == 1)
    {
        return 1;
    }
    return n * Factorial(n - 1);
}

Console.WriteLine(Factorial(3));  // 6

Paso a paso, en palabras

Main llama a Factorial(3).
Memoria nueva para Factorial con n = 3.
3 no es 1, así que el método llama a Factorial(2) y espera la respuesta.
Lo mismo otra vez: Factorial(2) llama a Factorial(1). Cada llamada tiene su propio n.
n es 1: este es el caso base. Devuelve 1 sin volver a llamar.
La respuesta baja: 2 * 1 = 2.
Y otra vez: 3 * 2 = 6.
Factorial(3) devuelve 6 y Main lo imprime.

Cada llamada recibe su propia memoria con su propio n. Se apilan una encima de otra y esperan. Esta pila se llama pila de llamadas (call stack). Cuando el caso base devuelve 1, las respuestas bajan una a una y la pila se deshace.

Pruébalo

Bajar y volver a subir

¿Qué imprimirá el programa?

static void Steps(int n)
{
    if (n == 0)
    {
        return;
    }
    Console.WriteLine("bajo " + n);
    Steps(n - 1);
    Console.WriteLine("subo " + n);
}

Steps(2);

Respuesta

bajo 2
subo 2
bajo 1
subo 1

bajo 2
bajo 1
subo 1
subo 2

bajo 2
bajo 1
subo 2
subo 1

Pruébalo

Encuentra el error

SumTo(4) debería devolver 1 + 2 + 3 + 4 = 10. En cambio, el programa se detiene con Stack overflow. ¿En qué línea está el error?

Elige la línea con el error.

La idea

¿Recursión o bucle?

El factorial se puede escribir con un bucle o con recursión. Aquí el bucle es la mejor opción: no acumula memoria por cada llamada, y para 100 000 llamadas la pila no alcanzará.

La recursión es natural donde algo contiene cosas más pequeñas del mismo tipo: una carpeta con carpetas dentro, una categoría con subcategorías, una rama con ramas. Te encontrarás con tareas así más adelante en el curso. Ahí un bucle se vuelve torpe, mientras que el método recursivo sigue siendo corto.

Más precisamente, para curiosos

El factorial se escribe a menudo con el caso base 0! = 1 (if (n == 0)). Así también funciona para 0.

Un int alcanza hasta 12!. Para 13! el resultado no cabe y el número sale mal. Para valores más grandes, usa long.

Pruébalo

Ordena las líneas

El método tiene que calcular una potencia: Power(2, 10) es 1024. Ordena sus líneas.

return b * Power(b, exp - 1);
{
}
static int Power(int b, int exp)
{
}
if (exp == 0)
return 1;

Ejercicio

Tareas recursivas

1. Factorial de dos formas. Escribe FactorialLoop(int n) con un bucle for y Factorial(int n) con recursión. Lee un número e imprime el resultado de los dos métodos.

El factorial de 5 es 120
El factorial de 5 es 120

2. Suma de cifras. SumDigits(int n): la última cifra (n % 10) más la suma de las cifras del resto (n / 10). El caso base es un número de una sola cifra.

3. Fibonacci. Cada número es la suma de los dos anteriores: 0, 1, 1, 2, 3, 5, 8… Fib(int n) devuelve el número n-ésimo. Pruébalo con 10, y después con 45. ¿Por qué es tan lento? Pista: ¿cuántas veces se calcula cada número?

4. Palíndromo. IsPalindrome(string s): la primera y la última letra son iguales, y el centro es un palíndromo. El caso base es una palabra de 0 o 1 letras.

SumDigits(2024)
Fib(10)
IsPalindrome("reconocer")
IsPalindrome("ABCDE")

8
55
True
False

Test

Ponte a prueba

1. ¿Qué es la recursión?Dos métodos con el mismo nombreUn bucle dentro de un métodoUn método que se llama a sí mismo

2. ¿Por qué un método recursivo necesita un caso base?Para que vaya más rápidoPara que pueda devolver un resultadoPara que deje de llamarse a sí mismo

3. Factorial(3) llama a Factorial(2), y esta llama a Factorial(1). ¿Cuántas variables n hay en memoria justo antes de que Factorial(1) devuelva su resultado?TresNingunaUna

4. ¿Qué pasa si nunca se llega al caso base?La pila se desborda y el programa se detiene con un errorEl programa se ejecuta sin fin, sin ningún errorEl método devuelve 0

Recursión

Cookies