Recursividad: una aplicación didáctica

Resumen

Una relación o ley de recurrencia define cada elemento de una sucesión como una combinación de los anteriores. Esto impide, a simple vista, calcular el enésimo elemento sin calcular previamente todos los que le preceden. Sin embargo, algunas de las sucesiones definidas por una ley de recurrencia también admiten una expresión explícita para el término general. En particular, tal expresión se puede obtener para cualquier relación de recurrencia conocida como lineal. Este trabajo busca desarrollar un algoritmo capaz de resolver o, en otras palabras, hallar una expresión explícita para muchas de estas relaciones de recurrencia lineales. Se muestra en este escrito el razonamiento detrás del algoritmo así como una explicación de su implementación en el lenguaje de Python. El trabajo forma parte de un proyecto organizado por el Departamento de Matemática Aplicada a las TIC denominado "Proyecto Calculadora". El desarrollo aquí mostrado conforma una librería dentro de lo que será una herramienta didáctica que pretende resolver algunos de los problemas vistos durante el grado en Matemáticas e Informática.

ABSTRACT

A recurrence relation defines each element of a sequence of numbers as a combination of the previous ones. At first glance, this prevents calculating the nth element without first calculating all preceding elements. However, some sequences defined by a recurrence relation also accept a closed-form expression for the general term. In particular, such an expression can be obtained for any recurrence relation known as linear. This work aims to develop an algorithm capable of solving or, in other words, finding a closed-form expression for many of these linear recurrence relations. This document presents the reasoning behind the algorithm as well as an explanation of its implementation in the Python language. This work is part of a project organized by the Department of Mathematics Applied to IT, called "Proyecto Calculadora". The software shown here constitutes a library within what will be an educational tool that aims to solve some of the problems encountered during the Mathematics and Computer Science degree.