34. Recursió

La recursivitat és una tècnica de programació que consisteix en una funció que es diu per resoldre un problema. Aquesta tècnica permet dividir un problema original en subproblemes similars però més simples.

Una funció recursiva consta de dues parts:

1. Solució de la caixa més senzilla o del cas base.

   Si la funció discuteix un problema senzill a resoldre, la solució es resol i es torna. En aquest cas, la funció no es diu.

2. Solució del cas més elaborat.

   Si la funció té com a argument un problema difícil de resoldre, el problema es divideix en problemes més petits i senzills i es crida a solucionar -los.

Exemple de funció recursiva per calcular el factorial d’un nombre. El factorial d’un nombre és la multiplicació de tots els números d’1 al número desitjat. Per exemple, el factorial de 6 és la multiplicació d’1 x 2 x 3 x 4 x 5 x 6.

El programa següent calcula el factorial d’un número recursiu

def factorial(n):
    if n <= 1:
        # Caso más sencillo
        return 1
    else:
        # Simplifica el problema y se llama a sí misma
        return n * factorial(n - 1)

print(factorial(6))  # Salida: 720

El programa següent retorna recursivament una cadena de text invertida

def invierte(texto):
    if len(texto) == 1:
        # Caso más sencillo
        return texto
    else:
        # Simplifica el problema y se llama a sí misma
        return texto[-1] + invierte(texto[:-1])

print(invierte('Hola, mundo'))

Sortida

odnum ,aloH

Quan es programi una funció recursiva, és important definir els casos o casos base més simples i assegurar -se que cada trucada recursiva s’acosta al cas base per evitar bucles infinits.

Algunes estructures de dades, com ara llistes enllaçades, arbres o directoris de disc dur, es poden definir i manipular recursivament més senzillament.

Exercicis

1. Definiu una funció recursiva que converteixi una llista de lletres en una sola cadena de text

   def texto(lista):
      ...
      ...
   
   print(texto(['H', 'o', 'l', 'a', ',', 'm', 'u', 'n', 'd', 'o'))
   

   Sortida

   Hola, mundo
   

2. Definiu una funció recursiva que compta del número que passa com a argument.

   Pista

   def cuenta_atras(n):
       if n == 0:
           ...
       else:
           ...
           ...
   
   cuenta_atras(10)
   

   Sortida

   10
   9
   8
   7
   6
   5
   4
   3
   2
   1
   ¡Despegue!
   

3. Definiu una funció recursiva anomenada Replicing que rebeu dos arguments `` Times's` i `` número ''. La funció ha de retornar una llista que aparegui `` number '' tantes vegades com diu la variable '`« temps' '.

   Pista

   def replicar(numero, veces):
       if veces <= 0:
           return []
       else:
           lista = ...
           lista = lista + [numero]
           return ...
   
   replicar(6, 10)
   

   Sortida

   [6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
   

4. Definiu una funció recursiva que inverteixi l’ordre dels dígits d’un número sense convertir -la en una cadena.

   Per obtenir l'últim dígit d'un número, podeu calcular el mòdul 10 del número. Per exemple, el 1234 % 10 serà igual a 4, l’últim dígit del número 1234.

   Pista

   def invierte(n, resultado=0):
       if n == 0:
           return resultado
       else:
           ultimo_digito = ...
           resultado = resultado * 10 + ultimo_digito
           return invierte( ... )
   
   print(invierte(12345)) # Salida: 54321