34. Recursion

Recursion is a programming technique that involves a function calling itself to solve a problem. This technique allows an original problem to be divided into similar but easier to solve subproblems.

A recursive function is made up of two parts:

1. Solution of the simplest case or base case.

   If the function has an easy-to-solve problem as an argument, it is solved and the solution is returned. In this case the function does not call itself.

2. Solution of the most elaborate case.

   If the function takes a hard-to-solve problem as an argument, it breaks the problem into smaller, easier problems and calls itself to solve them.

Example of a recursive function to calculate the factorial of a number. The factorial of a number is the multiplication of all numbers from 1 to the desired number. For example, the factorial of 6 is the multiplication of 1 x 2 x 3 x 4 x 5 x 6.

The following program calculates the factorial of a number recursively:

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

The following program returns an inverted text string recursively:

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'))

Exit:

odnum ,aloH

When programming a recursive function, it is important to define the simplest cases or base cases and ensure that each recursive call is close to the base case to avoid infinite loops.

Some data structures, such as linked lists, trees, or hard disk directories, can be more simply defined and manipulated recursively.

Exercises

1. Defines a recursive function that converts a list of letters into a single text string:

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

   Exit:

   Hola, mundo
   

2. Defines a recursive function that counts backwards from the number passed as an argument.

   Clue:

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

   Exit:

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

3. Defines a recursive function called replicate that takes two arguments times and number. The function must return a list in which number appears as many times as the variable times says.

   Clue:

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

   Exit:

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

4. Defines a recursive function that reverses the order of the digits of a number without converting it to a string.

   To obtain the last digit of a number you can calculate the module 10 of the number. For example, 1234 % 10 will be equal to 4, the last digit of the number 1234.

   Clue:

   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