C Piscine — C 05

El módulo de la recursión y la aritmética: factorial, potencia, Fibonacci, raíz cuadrada, primos y un cierre con las diez reinas. Casi todo se puede hacer de dos maneras — con un bucle o llamándose a sí misma— y el módulo te obliga a comparar ambas.

El concepto que vertebra el módulo: recursión vs. iteración — Una función iterativa resuelve el problema con un bucle y unas pocas variables: la memoria que usa es constante. Una función recursiva se llama a sí misma con un caso más pequeño hasta tocar un caso base; cada llamada pendiente ocupa un marco (stack frame) en la pila, con sus parámetros y su punto de retorno. C05 empareja deliberadamente factorial y potencia en versión iterativa y recursiva para que veas que resuelven lo mismo con costes distintos: la recursión es más corta y se lee como la definición matemática, pero cada nivel cuesta pila, y si te olvidas del caso base o no reduces el problema, la pila se desborda (stack overflow) y el programa muere. Entender esto aquí, con funciones de tres líneas, es lo que te permite después leer un árbol o un backtracking sin perderte. (El prólogo del enunciado cita al Sombrero Seleccionador de Harry Potter para acto seguido avisar de que el proyecto no va de magia; es el humor absurdo de costumbre.)

GGlosario de teoría

C 05 mezcla dos mundos: el de cómo se ejecuta una función que se llama a sí misma (la pila, los marcos, el caso base) y el de la aritmética entera (factorial, primos, raíces, desbordamientos). Aquí está cada término explicado desde cero y con un ejemplo sacado del propio módulo. En el resto de la página, la primera vez que sale uno de estos términos en cada tarjeta lleva un enlace a su entrada.

Recursión y pila

Iteración (función iterativa)

Resolver un problema repitiendo un bloque con un bucle (while) y unas pocas variables que van cambiando en cada vuelta. La función se llama una sola vez y hace todo el trabajo dentro de su bucle, así que la memoria que usa no crece con el tamaño del problema.

En C 05 son iterativas ex00 y ex02: ft_iterative_factorial(5) da cinco vueltas al bucle y devuelve 120, con las mismas dos variables de principio a fin.

Recursión (función recursiva)

Una función es recursiva cuando, para resolver un problema, se llama a sí misma con una versión más pequeña del mismo problema. Funciona porque cada llamada confía en que la siguiente devolverá la respuesta correcta para el caso pequeño, y solo tiene que añadir su parte.

Toda recursión correcta tiene dos piezas: un caso base que se responde sin volver a llamarse, y un paso recursivo que acerca el argumento a ese caso base. En ex01, ft_recursive_factorial(3) calcula 3 * ft_recursive_factorial(2), que calcula 2 * ft_recursive_factorial(1), y así hasta llegar a 0, que devuelve 1 sin llamar a nadie. Después las multiplicaciones se van resolviendo a la vuelta: 1, 1, 2, 6.

Caso base

El caso que una función recursiva sabe responder directamente, sin volver a llamarse. Es lo que hace que la recursión termine. Si falta, o si el paso recursivo no se acerca a él, la función se llama sin fin hasta agotar la pila.

En el módulo: 0! = 1 en el factorial, nb^0 = 1 en la potencia, y los dos casos base de Fibonacci (fib(0) = 0 y fib(1) = 1), porque cada término necesita los dos anteriores. En las reinas el caso base es «ya hay diez columnas colocadas»: se imprime la solución y se devuelve 1.

Pila de llamadas y marco (stack frame)

Cada vez que se llama a una función, el programa le reserva un trozo de memoria llamado marco (stack frame) con sus parámetros, sus variables locales y la dirección a la que volver al acabar. Los marcos se apilan unos encima de otros en una zona de memoria llamada pila (stack), y se quitan en orden inverso: el último en entrar es el primero en salir.

En una recursión hay tantos marcos a la vez como llamadas pendientes: ft_recursive_factorial(10) llega a tener once marcos apilados (del 10 al 0) antes de empezar a devolver. La versión iterativa usa uno solo. En las reinas, cada marco de ft_q_isolver guarda su propia copia del tablero pos[10] y su i, y por eso al volver de una rama el tablero del nivel anterior sigue intacto.

Desbordamiento de pila (stack overflow)

La pila tiene un tamaño fijo y pequeño: en este Linux, ulimit -s dice 8192 KB. Si una recursión apila más marcos de los que caben, el programa escribe fuera de la zona permitida y el sistema lo mata con un Segmentation fault.

Pasa con recursiones sin caso base y también con recursiones correctas pero demasiado profundas. Medido con el ex01 del repo: ft_recursive_factorial(1000000) termina con Segmentation fault (código de salida 139) antes de devolver nada, porque necesita un millón de marcos. El resultado ya habría sido basura por overflow, pero el programa ni siquiera llega a calcularlo.

Recursión en árbol y crecimiento exponencial

Cuando una función se llama a sí misma más de una vez en cada nivel, las llamadas forman un árbol: cada una abre dos ramas, cada rama otras dos… El número de llamadas crece de forma exponencial: con cada nivel de más, se multiplica por una cantidad fija.

Fibonacci es el ejemplo de libro. Contando las llamadas que hace la versión recursiva:

fib(10)  =        55      177 llamadas
fib(20)  =      6765    21891 llamadas
fib(30)  =    832040  2692537 llamadas
fib(40)  = 102334155  331160281 llamadas

Cada diez índices más, unas 120 veces más llamadas. ft_fibonacci(40) del repo tarda unos 0.8 s en esta máquina; con la misma proporción, fib(50) se iría a más de minuto y medio. El motivo es que se recalcula lo mismo muchas veces: fib(38) se calcula dos veces, fib(37) tres…

Memoización y programación dinámica

Dos formas de no repetir trabajo en una recursión en árbol. Memoizar es apuntar cada resultado la primera vez que se calcula (en un array, por ejemplo) y consultarlo después en vez de recalcularlo. La programación dinámica va al revés: calcula los casos pequeños primero y construye los grandes a partir de ellos, normalmente con un bucle.

No se usan en C 05 (el enunciado exige la versión recursiva de Fibonacci), pero en el ft_fibonacci.c del repo hay comentada una versión iterativa con dos variables que se van pisando: eso es programación dinámica reducida a lo mínimo, y cuesta n vueltas en vez de cientos de millones de llamadas.

Backtracking (vuelta atrás)

Una forma de buscar todas las soluciones de un problema construyéndolas paso a paso: en cada paso se prueba una opción; si no viola ninguna regla, se sigue al paso siguiente; si sí, o cuando se han agotado las opciones de ese paso, se vuelve al paso anterior y se prueba su siguiente opción. Las ramas imposibles se cortan en cuanto se detectan, sin explorarlas enteras.

En ex08 cada paso es una columna y cada opción una fila. Si la reina de la columna 3 choca con alguna anterior, no se mira ninguna de las 10⁶ formas de rellenar las columnas 4 a 9 a partir de ahí. La función del repo encuentra las 724 soluciones; la primera es 0257948136 y la última 9742051863, como en el ejemplo del enunciado.

Aritmética entera

Acumulador y elemento neutro

Un acumulador es una variable que va guardando un resultado parcial mientras un bucle recorre los datos: la suma hasta aquí, el producto hasta aquí. Tiene que empezar en el elemento neutro de la operación, el valor que no cambia nada: 0 para la suma (x + 0 = x) y 1 para el producto (x · 1 = x).

En ex00 y ex02 el acumulador empieza en 1 (p = 1, i = 1 en el repo). Si empezara en 0, todos los factoriales y todas las potencias darían 0. Y de paso, si el bucle no da ninguna vuelta, se devuelve el neutro: así salen solos 0! = 1 y 0^0 = 1.

Factorial (n!)

El producto de todos los enteros de 1 a n: 5! = 1·2·3·4·5 = 120. Por convención 0! = 1, y para negativos no está definido (el enunciado pide devolver 0). Cuenta de cuántas formas se pueden ordenar n cosas distintas.

Crece muy deprisa: 12! = 479001600 es el último que cabe en un int. 13! vale 6 227 020 800 y el ex00 del repo devuelve 1932053504, un valor sin sentido por overflow, que el enunciado permite no tratar.

Potencia (nb elevado a power)

Multiplicar un número por sí mismo varias veces: 2^10 = 2·2·…·2 (diez veces) = 1024. El exponente 0 da 1 en cualquier base, también 0^0, que en matemáticas se discute pero el enunciado fija en 1. Con exponente negativo el resultado sería una fracción (2⁻¹ = 0.5), que no cabe en un int: por eso se pide devolver 0.

Las dos versiones del repo dan (-2)^3 = -8, 2^-1 = 0 y 2^31 = -2147483648, este último ya por overflow.

Sucesión de Fibonacci

Cada término es la suma de los dos anteriores, empezando por 0 y 1: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… El enunciado cuenta desde el índice 0, así que ft_fibonacci(0) = 0, ft_fibonacci(1) = 1 y ft_fibonacci(10) = 55; con índice negativo pide −1.

De dónde viene: la popularizó Leonardo de Pisa, «Fibonacci», en su Liber Abaci de 1202, con un problema de cuántas parejas de conejos hay cada mes.

Operador % (resto) y divisibilidad

a % b es el resto de dividir a entre b con división entera: 17 % 5 = 2 porque 17 = 3·5 + 2. Si el resto es 0, b divide a a exactamente: nb % i == 0 es la forma de preguntar «¿i es divisor de nb?».

En C, con negativos el resto lleva el signo del dividendo: -17 % 5 = -2. Por eso en el ex04 de C 07 hace falta -(n % b) para sacar la cifra de un negativo. En ex06 el repo comprueba nb % i == 0 || - nb % i == 0, pero la segunda mitad sobra: a esa línea solo se llega con nb >= 2, y −nb % i es 0 exactamente cuando nb % i lo es.

Número primo

Un entero mayor que 1 cuyos únicos divisores son 1 y él mismo: 2, 3, 5, 7, 11, 13… El 1 no es primo (solo tiene un divisor) y el 0 tampoco, como recuerda el enunciado; los negativos no se consideran. El 9 no lo es porque 3 lo divide.

El mayor int, 2147483647, es primo. Por eso ft_find_next_prime siempre encuentra respuesta dentro del rango de int: con cualquier nb válido, como mucho llega a 2147483647. Con el repo: siguiente primo de −5 → 2, de 4 → 5, de 13 → 13 y de 14 → 17.

Raíz cuadrada entera y por qué basta probar hasta √n

La raíz cuadrada de n es el número que multiplicado por sí mismo da n. Es entera si ese número es entero, y entonces n es un cuadrado perfecto: 16 = 4·4. El 15 no tiene raíz entera, y ft_sqrt(15) devuelve 0.

Lo de «√n» vale también para los primos: los divisores van en parejas (36 = 2·18 = 3·12 = 4·9 = 6·6), y en cada pareja uno es como mucho √n. Si no hay ningún divisor hasta √n, no hay ninguno. Para 2147483647 eso es parar en 46 340 en vez de en más de dos mil millones. Medido: el ex06 del repo, que prueba hasta i < nb, tarda 9.3 s con 2147483647.

Tipos y lenguaje C

Desbordamiento de enteros (overflow) e INT_MAX

Un int ocupa 4 bytes y solo puede guardar valores entre −2147483648 (INT_MIN) y 2147483647 (INT_MAX). Si una operación da un resultado fuera de ese rango, se dice que desborda. En C, desbordar un entero con signo es comportamiento indefinido; en la práctica, en estas máquinas el valor «da la vuelta» y sale un número sin sentido, a menudo negativo.

En C 05 aparece por todas partes: 13!, 2^31, y sobre todo en i * i al buscar raíces. 46340² = 2147395600 cabe, pero 46341² = 2147488281 ya no. El enunciado permite no tratar el overflow del resultado en factorial, potencia y Fibonacci, pero no el de las cuentas intermedias, que pueden dejar un bucle sin parar.

long y cast para que el producto no desborde

long es un entero de 8 bytes en Linux de 64 bits: llega hasta unos 9·10¹⁸. Un cast es escribir el tipo entre paréntesis delante de una expresión, (long) i, para que se trate como de ese tipo. Si uno de los operandos de * es long, la multiplicación entera se hace en long.

El ex05 del repo deja i como int y hace la comparación en long: (long) i * i <= (long) nb. Con nb = INT_MAX el bucle para en 46341 sin desbordar y devuelve 0; con 2147395600 devuelve 46340.

Comportamiento indefinido (undefined behavior)

Lo que el estándar de C no define: el compilador puede hacer cualquier cosa, y «funciona en mi máquina» no garantiza nada. Ejemplos: desbordar un int, leer fuera de un array, desreferenciar NULL.

El enunciado lo usa como excepción: tus funciones no pueden hacer segfault «excepto en el caso de comportamientos indefinidos», y dice que con overflow «el valor devuelto queda indefinido». Por eso nadie te puede pedir un valor concreto para ft_iterative_factorial(13).

static en una función

Una función declarada static solo se ve dentro de su archivo .c. Sirve para los helpers: funciones auxiliares que nadie de fuera debe llamar ni puede chocar con otra del mismo nombre en otro archivo.

En ex07 tiene sentido marcar static la copia de ft_is_prime: si alguien compila tu ex07 junto con tu ex06, o con un main de pruebas que también la defina, dos funciones públicas con el mismo nombre dan multiple definition al enlazar. El repo la deja sin static; como cada ejercicio se compila aparte, no falla.

Coste: O(n), O(√n) y O(2ⁿ)

La notación O dice cómo crece el trabajo cuando crece la entrada, sin contar constantes. O(n): el doble de entrada, el doble de trabajo. O(√n): crece mucho más despacio (para n cien veces mayor, solo diez veces más trabajo). O(2ⁿ), exponencial: cada unidad de más multiplica el trabajo.

En C 05: el factorial y la potencia son O(n) en el número de vueltas o llamadas; ft_sqrt y la primalidad hasta √nb son O(√n); la primalidad hasta nb, como la del repo, es O(n); y Fibonacci recursivo es exponencial (crece como 1.618ⁿ, el número áureo).

ex00ft_iterative_factorial

Entrega: ft_iterative_factorial.cAutorizado: nada

Factorial iterativo: n! = 1·2·3·…·n. Si el argumento no es válido (negativo) devuelve 0; los desbordamientos no hay que tratarlos.

int	ft_iterative_factorial(int nb)
{
	int	result;
	int	i;

	if (nb < 0)
		return (0);
	result = 1;
	i = 1;
	while (i <= nb)
	{
		result *= i;
		i++;
	}
	return (result);
}

El acumulador arranca en 1 (el elemento neutro del producto), no en 0 — si empezara en cero todo el resultado sería cero. Con nb == 0 el bucle no se ejecuta y devuelve 1, que es la definición correcta de 0! = 1.

Qué te obliga a aprender — El patrón acumulador: una variable que guarda el resultado parcial mientras un índice recorre el rango. Es la forma iterativa canónica y la base de casi todos los bucles de cómputo que escribirás. Memoria constante, sin pila que crezca.

ex01ft_recursive_factorial

Entrega: ft_recursive_factorial.cAutorizado: nada

El mismo factorial, ahora recursivo.

int	ft_recursive_factorial(int nb)
{
	if (nb < 0)
		return (0);
	if (nb <= 1)
		return (1);
	return (nb * ft_recursive_factorial(nb - 1));
}

Dos guardas antes de recurrir: el caso de error (nb < 0 → 0) y el caso base (nb <= 1 → 1, que cubre tanto 0! como 1!). Solo cuando ninguno se cumple la función se llama a sí misma con nb - 1.

Qué te obliga a aprender — La estructura de toda función recursiva: primero el caso base que detiene la recursión, después el paso que reduce el problema hacia ese caso. La expresión nb * ft_recursive_factorial(nb - 1) es literalmente la definición matemática n! = n · (n-1)!. Compárala con el bucle de ex00: mismo resultado, pero aquí hay nb marcos apilados a la vez. Con un factorial da igual; con recursiones profundas empieza a importar.

ex02ft_iterative_power

Entrega: ft_iterative_power.cAutorizado: nada

Potencia iterativa nb^power. Si power < 0 devuelve 0; por definición 0^0 = 1.

int	ft_iterative_power(int nb, int power)
{
	int	result;

	if (power < 0)
		return (0);
	result = 1;
	while (power > 0)
	{
		result *= nb;
		power--;
	}
	return (result);
}

Multiplicar nb por sí mismo power veces. El caso 0^0 sale gratis: con power == 0 el bucle no entra y queda result = 1, que es la convención que pide el enunciado.

Qué te obliga a aprender — Que el elemento neutro importa. Igual que el factorial empieza en 1, la potencia también, porque 1 es el neutro del producto. Y que los casos límite (power cero o negativo) no son excepciones que gestionar aparte: se caen solos del diseño si eliges bien el valor inicial y la condición del bucle.

ex03ft_recursive_power

Entrega: ft_recursive_power.cAutorizado: nada

La misma potencia, recursiva.

int	ft_recursive_power(int nb, int power)
{
	if (power < 0)
		return (0);
	if (power == 0)
		return (1);
	return (nb * ft_recursive_power(nb, power - 1));
}

Caso base power == 0 → 1; paso nb^p = nb · nb^(p-1). Fíjate en que aquí el parámetro que se reduce es power, no nb: nb viaja intacto por toda la cadena de llamadas.

Qué te obliga a aprender — Que en una recursión no todos los argumentos cambian. Uno es el que decrece hacia el caso base (power) y otro es un dato fijo que se arrastra (nb). Distinguir cuál es cuál es exactamente lo que tendrás que hacer con recursiones de verdad, como el backtracking de ex08.

ex04ft_fibonacci

Entrega: ft_fibonacci.cAutorizado: nada

Devuelve el elemento index de Fibonacci (0, 1, 1, 2, 3, 5…), con el primero en el índice 0. Debe ser recursiva. Si index < 0 devuelve -1.

int	ft_fibonacci(int index)
{
	if (index < 0)
		return (-1);
	if (index == 0)
		return (0);
	if (index == 1)
		return (1);
	return (ft_fibonacci(index - 1) + ft_fibonacci(index - 2));
}

Aquí hay dos casos base (0 y 1) porque cada término depende de los dos anteriores, y dos llamadas recursivas por nivel.

Qué te obliga a aprender — La recursión en árbol, y su lado oscuro. fib(n) vuelve a calcular fib(n-2) por dos caminos distintos, y fib(n-3) tres veces, y así: el número de llamadas crece exponencialmente. fib(40) ya hace 331 160 281 llamadas, más de trescientos millones. El enunciado exige la versión recursiva justamente para que sientas esa explosión, y para que más adelante entiendas por qué existen la memoización y la programación dinámica. La versión iterativa (dos variables que se van pisando) lo haría en O(n) y sin pila; que la piscine te prohíba usarla aquí es pedagógico, no práctico.

ex05ft_sqrt

Entrega: ft_sqrt.cAutorizado: nada

Raíz cuadrada entera: devuelve la raíz si es exacta, o 0 si no lo es (o si nb no tiene raíz entera).

int	ft_sqrt(int nb)
{
	long	i;

	if (nb < 1)
		return (0);
	i = 1;
	while (i * i < nb)
		i++;
	if (i * i == nb)
		return (i);
	return (0);
}

Se prueban candidatos 1, 2, 3… hasta que i·i alcanza o supera nb. Si lo iguala exactamente, esa es la raíz; si lo supera sin igualarlo, nb no es un cuadrado perfecto y la respuesta es 0.

Qué te obliga a aprender — Dos cosas. (1) El desbordamiento como problema de tipos: i·i puede superar los ~2.147 millones que aguanta un int antes de que i llegue a la raíz de un nb grande. Declarar i como long evita que el producto se desborde y el bucle nunca pare. Es tu primer encuentro con "el tipo importa aunque el resultado quepa". (2) Que a veces el algoritmo obvio (probar en orden) es suficiente; optimizarlo con búsqueda binaria es una mejora que puedes razonar después.

ex06ft_is_prime

Entrega: ft_is_prime.cAutorizado: nada

Devuelve 1 si nb es primo, 0 si no. Ni 0 ni 1 son primos (ni los negativos).

int	ft_is_prime(int nb)
{
	long	i;

	if (nb < 2)
		return (0);
	i = 2;
	while (i * i <= nb)
	{
		if (nb % i == 0)
			return (0);
		i++;
	}
	return (1);
}

La clave está en la condición i·i <= nb: no hace falta probar divisores más allá de la raíz cuadrada de nb, porque si nb tuviera un divisor mayor que su raíz, su pareja sería uno menor que ya habríamos encontrado.

Qué te obliga a aprender — Optimización por razonamiento matemático, no por trucos de código. Comprobar divisores hasta nb funciona pero es lento; parar en √nb convierte un O(n) en O(√n) y solo requiere entender por qué los divisores vienen en parejas. Otra vez long para que i·i no se desborde con primos grandes. La aritmética de % (resto) es el detector de divisibilidad de todo el módulo.

ex07ft_find_next_prime

Entrega: ft_find_next_prime.cAutorizado: nada

Devuelve el primo inmediatamente superior o igual a nb.

static int	ft_is_prime(int nb)
{
	/* … idéntica a ex06 … */
}

int	ft_find_next_prime(int nb)
{
	while (!ft_is_prime(nb))
		nb++;
	return (nb);
}

Se prueba nb, y si no es primo se sube de uno en uno hasta encontrar el primero que lo sea. Como el propio nb cuenta, si ya es primo se devuelve tal cual.

Qué te obliga a aprender — La reutilización como diseño: en vez de reescribir la primalidad, la encapsulas en un helper y la llamas. Como el helper no debe verse desde fuera del archivo, se declara static — tu primera decisión consciente de ámbito (qué es público y qué es privado dentro de un .c). La Norma limita a 5 funciones por archivo y este es un buen ejemplo de por qué partir un problema en piezas pequeñas ayuda a que cada una quepa y se lea.

ex08ft_ten_queens_puzzle

Entrega: ft_ten_queens_puzzle.cAutorizado: write

Mostrar todas las formas de colocar diez reinas en un tablero 10×10 sin que ninguna ataque a otra, y devolver el número total de soluciones (son 724). Cada solución se imprime como diez cifras: la n-ésima cifra es la fila de la reina en la columna n.

static int	is_valid(int *board, int col, int row)
{
	int	i;

	i = 0;
	while (i < col)
	{
		if (board[i] == row)
			return (0);
		if (col - i == row - board[i] || col - i == board[i] - row)
			return (0);
		i++;
	}
	return (1);
}

static int	solve(int *board, int col)
{
	int	row;
	int	count;

	if (col == 10)
	{
		print_board(board);
		return (1);
	}
	row = 0;
	count = 0;
	while (row < 10)
	{
		if (is_valid(board, col, row))
		{
			board[col] = row;
			count += solve(board, col + 1);
		}
		row++;
	}
	return (count);
}

El truco de la representación: como cada columna lleva exactamente una reina, board[col] = row basta para describir el tablero, y así dos reinas nunca comparten columna por construcción. is_valid solo tiene que comprobar, contra las reinas ya colocadas, la misma fila (board[i] == row) y las dos diagonales (cuando la distancia en columnas iguala la distancia en filas).

Qué te obliga a aprender — El backtracking, que es la síntesis de todo C05. solve avanza columna a columna probando filas; cuando una fila es válida la fija y baja un nivel (recursión), y cuando agota las diez filas de una columna simplemente vuelve — "deshace" — y prueba la siguiente opción del nivel anterior. La pila de llamadas es el tablero parcial: no necesitas guardar y restaurar estado a mano porque cada marco recuerda su propio col y su propio row. Colocar el caso base (col == 10: solución completa, imprime y suma 1) y acumular los retornos de las ramas es el mismo esqueleto del factorial recursivo, pero ramificado. Si entiendes por qué esto explora exactamente todas las combinaciones válidas y ninguna inválida, tienes la llave de laberintos, sudokus y parsers.

?Preguntas probables de la evaluación

Lo que es fácil que pregunte quien te evalúe, con una respuesta corta y el enlace a la sección donde está explicado. Están agrupadas en: recursión, casos límite, rendimiento y Norma. Las respuestas hablan del código de tu entrega (repo/), que no siempre es el mismo que se muestra en las tarjetas. Antes de mirar la respuesta, intenta contestar tú.

Recursión

¿Qué diferencia hay entre tu factorial iterativo y el recursivo?

El resultado es el mismo. El iterativo usa un bucle y un acumulador que empieza en 1: un solo marco en la pila, memoria constante. El recursivo se llama con nb - 1 hasta el caso base nb == 0, así que con nb = 10 hay once marcos apilados a la vez y las multiplicaciones se hacen a la vuelta. → ex00, ex01, pila de llamadas

¿Qué pasa si quitas el caso base de una función recursiva?

Que nunca deja de llamarse: cada llamada añade un marco hasta que la pila se llena y el programa muere con Segmentation fault. Tampoco hace falta quitarlo: con el caso base bien puesto, ft_recursive_factorial(1000000) también revienta la pila (código 139) porque necesita un millón de marcos. → desbordamiento de pila

¿Por qué ft_fibonacci(40) tarda casi un segundo? ¿Cómo lo mejorarías?

Porque cada llamada hace dos llamadas, y se recalculan los mismos términos una y otra vez: fib(40) hace 331 160 281 llamadas. Se arregla guardando los resultados (memoización) o con un bucle de dos variables, como la versión comentada en tu archivo, que hace 40 vueltas. El enunciado exige la recursiva, así que se entrega esa. → ex04, recursión en árbol

Explícame tus diez reinas. ¿Cómo detectas las diagonales?

pos[col] = fila: una reina por columna, así que nunca comparten columna. ft_q_isolver prueba las diez filas de la columna p; si ft_q_ava la acepta, baja a p + 1, y al llegar a p == 10 imprime y devuelve 1. Dos reinas están en la misma diagonal cuando la diferencia de filas es igual a la de columnas (pos[i] ± (p - i) == pos[p]). Las columnas aún vacías valen −100 y no chocan nunca. Total: 724. → ex08, backtracking

Casos límite

¿Qué devuelve cada función con un argumento negativo?

Lo que pide cada enunciado: los factoriales, 0; las potencias con power < 0, 0; ft_fibonacci, −1; ft_sqrt y ft_is_prime, 0; ft_find_next_prime(-5), 2, porque sube hasta el primer primo. Comprobado con el repo. → ex00, ex04, ex07

¿Cuánto valen 0!, 0^0 y ft_is_prime(1)?

0! = 1 y 0^0 = 1: el bucle no da ninguna vuelta y se devuelve el valor inicial, 1, que es el neutro del producto. En la versión recursiva son el caso base. ft_is_prime(0) y ft_is_prime(1) dan 0: el enunciado lo dice expresamente. → acumulador y elemento neutro, primo

¿Por qué ft_sqrt(2147483647) no se queda colgado?

Porque la condición se calcula en long: (long) i * i <= (long) nb. Con int, 46341² desbordaría, saldría negativo y el bucle seguiría para siempre. Con long, en 46341 el producto supera a nb, el bucle para y devuelve 0. → ex05, long y cast

¿Qué devuelve ft_iterative_factorial(13)?

1932053504, que no es 13! (6 227 020 800): no cabe en un int. El enunciado dice que el overflow no hay que tratarlo y que el valor queda indefinido; el último factorial correcto es 12! = 479001600. → factorial, overflow

Rendimiento (mejor tener la respuesta preparada)

¿Cuánto tarda tu ft_is_prime(2147483647)?

Unos 9 segundos medidos, porque el repo prueba divisores hasta i < nb: más de dos mil millones de divisiones. Si la prueba tiene límite de tiempo, puede dar timeout, y lo mismo ft_find_next_prime, que usa la misma función. La mejora es parar en (long) i * i <= nb: unas 46 000 vueltas, como en la tarjeta de ex06. → ex06, por qué basta hasta √n

¿Por qué ex07 lleva su propia copia de ft_is_prime?

Porque cada ejercicio se entrega y se compila solo: ex07 no puede usar el archivo de ex06. Lo limpio es marcarla static, para que no se vea fuera del archivo ni choque con otra ft_is_prime; en el repo no lo está. → ex07, static

Norma y entrega

¿Pasa la Norma? ¿Qué es -R CheckForbiddenSourceHeader?

El enunciado pide pasar norminette con ese flag, y la Moulinette lo usa también. Con la versión 3.3.59 instalada, los nueve archivos dan OK!. Funciones autorizadas: ninguna de ex00 a ex07 y solo write en ex08; el #include <unistd.h> que llevan todos no llama a nada, pero solo hace falta en ex08. El main de pruebas de ft_fibonacci.c está comentado, que es lo que permite el enunciado. → ex08