En el mundo de la informática, la recursividad es un método en el que la solución a un problema depende de instancias más pequeñas del mismo problema. Es un proceso en el que una función se llama a sí misma como una subrutina. Esto permite llamar a la función con menos argumentos, lo que reduce la cantidad de información de estado que la función debe mantener y proporciona un medio muy elegante y conciso para expresar soluciones a algunos tipos de problemas. La recursividad a menudo se considera un concepto difícil de comprender para los principiantes. Sin embargo, cuando se entiende correctamente, puede ser una herramienta extremadamente poderosa en el arsenal de un programador. Puede ayudar a crear un código más limpio y conciso y, a menudo, puede usarse para resolver problemas complejos con soluciones simples y elegantes.

En esta lección, aplicaremos la recursividad a la secuencia de Fibonacci, que es una serie de números donde un número es la suma de los dos últimos números, es decir, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, etc. La secuencia comienza desde 0, por lo que el enésimo número es la suma de (n-1)ésimo y (n-2)ésimo número.

Vistas recursivas en SmartPy

En SmartPy, la recursividad se implementa permitiendo que una función se llame a sí misma dentro de su propia definición. Este método es extremadamente útil cuando se trata de problemas que se pueden dividir en subproblemas más pequeños e idénticos. Una vista recursiva en SmartPy es esencialmente una vista que utiliza recursividad. Una vista es una función de SmartPy que no modifica el almacenamiento del contrato pero puede leerlo. Cuando hablamos de una vista recursiva, nos referimos a una función de vista que se llama a sí misma durante su ejecución.

Secuencia Fibonacci

La secuencia de Fibonacci es un conjunto de números donde cada número es la suma de los dos anteriores, comenzando por 0 y 1. Esta secuencia, aunque simple, proporciona una base excelente para comprender la recursividad debido a su naturaleza recursiva.

La secuencia de Fibonacci está definida por la relación de recurrencia:

SCSS 
 F(n) = F(n-1) + F(n-2)

Siendo las condiciones iniciales F(0) = 0 y F(1) = 1. Esto significa que para obtener el n-ésimo número en la secuencia de Fibonacci, sumamos el (n-1) -ésimo y el (n-2) -ésimo número. Esta naturaleza recursiva es exactamente lo que hace que la secuencia de Fibonacci sea perfecta para comprender la recursividad. Ahora que comprendemos mejor la recursividad y cómo se aplica a la secuencia de Fibonacci, profundicemos en el código SmartPy que implementa una vista recursiva para calcular la secuencia de Fibonacci.

Tutorial de código

El código SmartPy dado define un contrato, FibonacciView, que calcula la secuencia de Fibonacci utilizando una vista recursiva. Este es un gran ejemplo para comprender cómo se crean y utilizan funciones recursivas en SmartPy.

Python 
 importa smartpy como sp 


 @sp.module 
 def main(): 
 class FibonacciView(sp.Contract): 
 """Contrato con una vista recurrente para calcular la suma de números de Fibonacci."""

        @sp.onchain_view() 
 def fibonacci(self, n): 
 """Devuelve la suma de los números de Fibonacci hasta el n.

            Args: 
 n (sp.int): número de números de Fibonacci a sumar.
            Retorno: 
 (sp.int): la suma de los números de Fibonacci 
 """ 
 sp.cast(n, int) 
 si n < 2: 
 devuelve n 
 más: 
 n1 = sp.view("fibonacci", sp.self_address(), n - 1, int).unwrap_some() 
 n2 = sp.view("fibonacci", sp.self_address(), n - 2, int).unwrap_some()
                devuelve n1 + n2 


 si las "plantillas" no están en __name__: 

 @sp.add_test(name="Escenario básico de FibonacciView", is_default=True) 
 def basic_scenario(): 
 sc = sp.test_scenario(main)
        sc.h1("Escenario básico.")
        sc.h2("Origen.")
        c1 = principal.FibonacciView() 
 pb += c1 
 sc.verify(c1.fibonacci(8) == 21)

Este contrato FibonacciView tiene una función de vista recursiva, fibonacci, que devuelve el enésimo número de Fibonacci.

La función está decorada con @sp.onchain_view(), lo que indica que se trata de una operación de solo lectura en el almacenamiento del contrato. Esta función toma un número entero n como argumento, que representa la posición en la secuencia de Fibonacci que queremos recuperar.

Dentro de la función, primero convertimos n a un número entero por seguridad. La parte recursiva de la función viene a continuación. Si n es menor que 2, simplemente devolvemos n porque los dos primeros números de la secuencia de Fibonacci son 0 y 1. Si n es mayor o igual a 2, calculamos el enésimo número de Fibonacci llamando recursivamente a la función fibonacci para n-1 y n-2 y luego sumando los resultados. Esto corresponde a la relación de recurrencia que define la secuencia de Fibonacci. Las llamadas sp.view crean estas llamadas recursivas a la propia función fibonacci .

Uso de un bucle para lograr eficiencia 
 Si bien la recursividad es un concepto valioso para la comprensión, es importante tener en cuenta que puede ser menos eficiente y requerir más recursos computacionales, especialmente cuando se trata de números grandes. Para evitar problemas como el desbordamiento de la pila, un enfoque más eficiente sería utilizar un bucle para calcular la secuencia de Fibonacci y almacenar los números de Fibonacci calculados en un contrato separado.
Aquí hay un ejemplo de alto nivel de cómo puede modificar el contrato FibonacciView para usar un bucle: 
 Este contrato modificado, FibonacciCalculator, usa un bucle para calcular eficientemente los números de Fibonacci y los almacena en el almacenamiento del contrato. Luego puede llamar al punto de entrada calcular_fibonacci para recuperar el enésimo número de Fibonacci.
Este enfoque es más eficiente en cuanto a recursos y adecuado para valores mayores de n.

Python 
 @sp.moduledef main(): 
 clase FibonacciCalculator(sp.Contract): 
 """Contrato para calcular eficientemente la secuencia de Fibonacci."""def __init__(self): 
 self.init(almacenamiento=sp.map(tkey=sp.TInt, tvalue=sp.TInt).set(0, 0).set(1, 1)) 

 @sp.entry_pointdef calcular_fibonacci(self, n): 
 sp.verify(n >= 0, message="n debe ser no negativo") 
 almacenamiento = self.data 
 para i en rango(2, n + 1): 
 next_fib = almacenamiento[i - 1] + almacenamiento[i - 2] 
 almacenamiento = almacenamiento.set(i, next_fib) 
 sp.result(almacenamiento[n])

Sigamos con la sección de pruebas.

En la función de prueba basic_scenario, creamos una nueva instancia del contrato FibonacciView , la agregamos a nuestro escenario y luego usamos sc.verify para verificar que el octavo número de Fibonacci sea 21, lo cual es cierto para la secuencia de Fibonacci.

Ejecutando el código en SmartPy IDE

Para ejecutar el código:

1. Abra el IDE de SmartPy.

2. Copie y pegue el código proporcionado en el editor.

3. Haga clic en el botón "Ejecutar". Debería ver el escenario de prueba ejecutándose en el lado derecho del IDE. Verá las operaciones que se realizan y los controles que se verifican.
   Esta lección ha cubierto mucho terreno. Hemos pasado de los conceptos básicos de la recursividad y cómo se usa en programación, a las vistas recursivas en SmartPy, e incluso aplicamos estos conceptos a la secuencia de Fibonacci. También exploramos un ejemplo de código funcional en SmartPy y aprendió cómo ejecutar y verificar este código en el IDE de SmartPy.