Recursividad en Python.

[jgalveg]

Estoy siguiendo el libro de python de la Universidad Jaume I que circula por internet y voy por la recursividad. Si alguien conoce el libro sabrá que va mucho de matemáticas.

Los ejercicios me parecen muy complicados en general y me gustaría saber donde podría encontrar ejercicios de recursividad que fueran desde los más simple e ir complicándose poco a poco.

En general, en todos los temas y como estoy siguiendo un ciclo a distancia la cosa va muy rápida y no termino de pillar las cosas. Estoy muy verde en listas, matrices y la recursividad. En general, mi problema es que tardo demasiado en plantear un programa.

Por eso les pido ayuda. Ejercicios que empiezen desde los más sencillo hasta los más complicado.

Muchas gracias.

[_cronos2]

La recursividad podría definirse como el arte de hacer que una cosa se llame a sí misma hasta que tú quieras Los ejemplos típicos son la sucesión de Fibonacci, o el algoritmo de ordenación Quicksort.
Para Fibonacci:

Código Python:

def fibo(n):
    a, b = 0, 1
    while a < n:
        print a, b
        a, b = b, a + b
 

Lo he puesto de memoria, creo que está bien Esto muestra los términos de la sucesión de Fibonacci menores que un número n
Esto puede hacerse recursivamente si quieres calcular el término n de la sucesión:

Código Python:

def fibo(n):
    return 1 if n <= 2 else fibo(n - 1) + fibo(n - 2)
 

Si el término es 2 o menos, devolvemos 1, si es mayor calculamos la suma de los dos anteriores términos de la sucesión. Fíjate que si n es 4, por ejemplo, hay que añadir un nivel más de recursión, porque n - 1 sería 3, y por tanto fibo(3) tendría que calcular fibo(2) + fibo(1).
Como podrás imaginar, cuanto mayor sea n mucho mayor será el número de cálculos que habrá que hacer, por eso los algoritmos recursivos no suelen ser muy eficientes a la larga.
PD: El primer snippet no contiene nada de recursión, era sólo para mostrar qué es la sucesión de Fibonacci por si no la conocías, aunque si dices que hay tantas matemáticas puede que sí sepas de qué hablo.
Espero que te haya ayudado.
Saludos (:
PD2: Pregunta mamporrera, si vives en Canarias, ¿cómo es que estudias en la UJI de Castellón?

[jgalveg]

Muchas gracias si conozco los ejemplos de fibonacci, factorial, etc... Pero necesito ejercicios para yo intentar hacerlos y que sean sencillos.

Referente a lo de Castellón es porque el el ciclo utilizan ese libro.

Gracias otra vez.

[gonzo13]

Un ejercicio que puede resolverse mediante recursividad, aunque quizás sea algo tedioso (que no complicado), es el de calcular el determinante de una matriz cuadrada de orden mayor que 2 haciendo desarrollo por filas o columnas. Es decir, no haciendo los determinantes de orden 2, sino volviendo a desarrollar por filas.

Te aconsejo que depures bien tu programa y lo ejecutes un par de veces "a mano" para detectar errores.

Un saludo,
gonzo.

[razpeitia]

Antes de empezar recursividad (y suponiendo que sabes ciclos) tienes que definir mas formalmente que es recursividad y como funciona.

¿Que es recursividad?
Sacado de la wikipedia: Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición.

Esto puede ser algo confuso, pero sigamos adelante y nos quedemos atorados en la definición "formal".

¿Como funciona la recursividad en programación?
Una función recursiva siempre debe de tener 2 partes.
La condición de parada y el caso general. Si lo traducimos en un ciclo while este sería la condición de parada y el cuerpo del while.

Ahora vamos a definir una propiedad muy interesante:
Cualquier algoritmo iterativo puede ser traducido a uno recursivo y viceversa

Veamos un ejemplo de un ciclo while a una función recursiva.

Código Python:

#While
i = 0
while i < 10:
    print i
    i += 1
 
#Recursivo
def f(i):
    if i < 10:
        print i
        f(i+1)
f(0)
 

Ten en mente que esto es exponencial así que ten cuidado cuando utilices recursión de orden 2 o mayor.

Si quieres ejercicios puedes pensar en escribir tus programas iterativos en recursivos.

[ramoncordero]

A ver si entendí, en poca palabras con una recursividad se logra la solución de un problema ( algoritmo ) utilizando su propias funciones.

Recursividad : Amanecí con hambre no hay mucho en la nevera y es muy temprano para ir al supermercado, así que tendré que comer lo que se encuentra en las distintas secciones que se encuentran dentro del refrigerador.

Edito : ahora mismo inconscientemente use recursividad al eliminar una carpeta en Linux con el comando rm -r

[jgalveg]

Muchas gracias a todos por las respuestas. Entiendo la recursividad, entiendo los pocos ejercicios que he podido ver. Pero de ahí a que yo dasarrolle uno propio, eso no soy capaz.
Gracias a todos.