Un programa informático es recursivo si se ejecuta a sí mismo durante su ejecución. Sin ningún ejemplo, esta frase resulta difícil de entender… y aún es más difícil comprender por qué hoy todos los lenguajes de programación utilizan la recursividad, cuando los primeros, como Cobol para la gestión o Fortran para el cálculo científico, prescindían de ella. Una de las razones es la seguridad de los programas recursivos, prácticamente los únicos de los que se puede demostrar que hacen realmente lo que se supone que deben hacer…
Inducción y juegos de cartas
======================================================================================================
Tome una baraja de cartas, barájela e intente ordenarla. ¿Cómo hacerlo? A priori, la tarea es compleja. El principio de inducción permite simplificarla considerablemente planteando la cuestión de otro modo: imagine que supiera ordenar n cartas; ¿cómo ordenar n + 1? Dicho de forma más prosaica, sabe ordenar una baraja de cuatro cartas. Le dan una más; ¿qué hace?
Naturalmente, ordena las cuatro primeras e inserta la quinta en su lugar. Para ello, basta con compararla sucesivamente con las cartas ya ordenadas, empezando por la primera. Aquí, la nueva carta se inserta después de la segunda. ¡Este método se basa exactamente en la idea de inducción! Para convencerse de ello, formalicémoslo al estilo de las demostraciones por inducción. He aquí, pues, un método que, dada una baraja T, devuelve la misma baraja ordenada:
