RECURSIVIDAD

Se dice que una función es recursiva cuando se llama a si

misma.

No todas la funciones pueden llamarse a si mismas, deben

estar diseñadas especialmente para que sean recursivas,

de otro modo podrían conducir a bucles infinitos, o a que el

programa termine inadecuadamente.

RECURSIVIDAD

Cuando se llama a una función, se crea un nuevo juego de

variables locales, de este modo, si la función hace una

llamada a si misma, se guardan sus variables y parámetros.

La nueva instancia de la función trabajará con su propia

copia de las variables locales, cuando esta segunda instancia

de la función retorna, recupera las variables y los

parámetros anteriores y continúa la ejecución en el punto

en que había sido llamada.

RECURSIVIDAD

La serie de pasos recursivos debe ser finita, terminando

con un paso base.  

Es decir, a cada paso recursivo se le reduce el número

de pasos que hay que dar para terminar, llegando un

momento en el que no se verifica la condición de paso a la

recursividad.  

NOTA: Toda función recursiva se puede resolver de forma

Iterativa y viceversa

PASO BASE

EJEMPLOS DE RECURSIVIDAD

Función recursiva para calcular el factorial de un número

entero.

El factorial se simboliza como n!, se lee como "n

factorial", y la definición es:

n! = n * (n-1) * (n-2) * ... * 1

No se puede calcular el factorial de números negativos,

y el factorial de cero es 1, de modo que una función bien

hecha para cálculo de factoriales debería incluir un control

para esos casos:

FACTORIAL

DE NUMERO ENTERO A BINARIO-En este tipo de conversión

no es necesario usar recursividad.-Se puede usar otros métodos.

?POR QUE ES RECURSIVO ESTE CASO?

NUMERO ELEVADO A SU EXPONENTE

Leonardo de Pisa

(c. 1170 - 1250), también

llamado Fibonacci, fue un

matemático italiano, famoso

por la invención de la

sucesión de Fibonacci,

surgida como consecuencia

del estudio del crecimiento de

las poblaciones de conejos, y

por su papel en la

popularización del sistema de

numeración posicional en

base 10 (o decimal) en

Europa.

Fibonacci

Resolver la serie de Fibonacci por recursividad0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

Johann Carl Friedrich Gauss

(30 de abril de 1777 – 23 de

febrero de 1855), fue un

matemático, astrónomo y físico

alemán.

Cuando tenía 10 años en la

escuela el maestro les manda

como penitencia sumar los

cien primeros números

naturales.

Transcurridos pocos segundos

Gauss levanta la mano y dice

tener la solución: los cien

primeros números naturales

suman 5.050.

Carl Friedrich Gauss

¿Cómo lo hizo Gauss? Mentalmente se dio cuenta de

que la suma de dos términos equidistantes era constante:

1 , 2 , 3 , 4 . . . . . . . . 97 , 98 , 99 , 100

1+100 = 2+99 = 3+98 = 4+97 = ... = 101

Con los 100 números se pueden formar 50 pares, de

forma que la solución final viene dada por el producto

101· 50 = 5050

Carl Friedrich Gauss

Ingresar un número y calcular su sumatoria

Debe sumarse todos los número que le anteceden

Probar la sumatoria de Gauss

FUNCIONES

Una función es un conjunto de líneas de código que realizan una tarea específica y puede retornar un valor.

DEFINICION

Esta definición proviene de la definición de función matemática la cual posee un dominio y un rango, es decir un conjunto de valores que puede tomar y un conjunto de valores que puede retornar luego de cualquier operación.

Son argumentos de entrada para usarse dentro de la función.

Hay algunos detalles respecto a los argumentos de una función, veamos:

Una función o procedimiento pueden tener una cantidad cualquier de parámetros, es decir pueden tener cero, uno, tres, diez, cien o más parámetros. Aunque habitualmente no suelen tener más de 4 o 5.

Si una función tiene más de un parámetro cada uno de ellos debe ir separado por una coma.

Los argumentos de una función también tienen un tipo y un nombre que los identifica. El tipo del argumento puede ser cualquiera y no tiene relación con el tipo de la función.

¿QUÉ SON LOS PARÁMETROS?

Las funciones son utilizadas para descomponer grandes problemas en tareas simples y para implementar operaciones que son comúnmente utilizadas durante un programa y de esta manera reducir la cantidad de código.

¿PARA QUÉ SE USA LAS FUNCIONES?

Cuando una función es invocada se le pasa el control a la misma, una vez que esta finalizó con su tarea el control es devuelto al punto desde el cual la función fue llamada.

Las funciones, como subalgoritmos que son, tienen una constitución similar a los algoritmos. Por consiguiente, una función constará de:

Cabecera, con la definición de la función. Cuerpo de la función.

DECLARACIÓN DE UNA FUNCIÓN EN C++

Dentro del cuerpo de la función estará el bloque de declaraciones y el bloque de instrucciones. Este debe incluir una instrucción mediante la que la función tomará un valor para devolverlo al algoritmo llamador.

Luego de la definición de la "firma" de la función, se define su funcionamiento entre llaves; todo lo que esté dentro de las llaves es parte del cuerpo de la función y éste se ejecuta hasta llegar a la instrucción return.

Debes tener en cuenta dos cosas importantes con la sentencia return:

Cualquier instrucción que se encuentre después de la ejecución de return NO será ejecutada. Es común encontrar funciones con múltiples sentencias return al interior de condicionales, pero una vez que el código ejecuta una sentencia return lo que haya de allí hacia abajo no se ejecutará.

El tipo del valor que se retorna en una función debe coincidir con el del tipo declarado a la función, es decir si se declara int, el valor retornado debe ser un número entero.

CONSEJOS ACERCA DE RETURN

El nombre de la función debe coincidir

exactamente al momento de invocarla. El orden de los parámetros y el tipo debe coincidir. Invocar una función sigue siendo una sentencia

habitual de C++, así que ésta debe finalizar con ';' como siempre.

El valor retornado por una función puede ser asignado a una variable del mismo tipo.

Una función puede llamar a otra dentro de sí misma o incluso puede ser enviada como parámetro a otra.

DETALLLES PARA INVOCAR FUNCIONES

Es la función principal en C++. La diferencia de esta función con otras funciones es que no se necesita llamar a esta función, ya que el compilador de C++ busca la función main y la ejecuta automáticamente.

El return de la función main es cero, que significa que no hay error, pero no se suele colocar.

Todo programa C++ tiene una función llamada main. La función main es el punto de entrada al programa y también el punto de salida.

FUNCIÓN MAIN

Bajo ciertas circunstancias se deseará escribir funciones que no regresen valor alguno y para ello podemos declarar a la función como void. La palabra reservada void es utilizada para declarar funciones sin valor de retorno y también para indicar que una función específica no requiere de parámetros.

La función void termina cuando se ejecuta la última sentencia de la función. No necesita return.

FUNCIÓN VOID

ALGORITMO DE BACKTRACKING

En su forma básica, la idea de backtracking se asemeja a un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol, o por lo menos no contiene ciclos. Sea cual sea su estructura, existe sólo implícitamente. El objetivo del recorrido es encontrar soluciones para algún problema.

El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede bien detenerse (si lo único que se necesita es una solución del problema) o bien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución

ALGORITMO DE BACKTRACKING

proc Backtracking (↕X[1 . . . i ]: TSolución, ↑ok: B)

variables L: ListaComponentesiniciosi EsSolución (X) entoncesok CIERTOde lo contrariook FALSOL=Candidatos (X)mientras ¬ok ^ ¬Vacía (L) hacerX[i + 1] Cabeza (L); L Resto (L) Backtracking (X, ok) fin mientrasfin sifin

ENFOQUESALGORITMO DE BACKTRACKING

Los problemas que deben satisfacer un determinado tipo de restricciones son problemas completos, donde el orden de los elementos de la solución no importa. estos problemas consisten en un conjunto (o lista) de variables a la que a cada una se le debe asignar un valor sujeto a las restricciones del problema. la técnica va creando todas las posibles combinaciones de elementos para obtener una solución. su principal virtud es que en la mayoría de las implementaciones se puede evitar combinaciones, estableciendo funciones de acotación (o poda) reduciendo el tiempo de ejecución.vuelta atrás está muy relacionado con labúsquedas binarias .

DISEÑO E IMPLEMENTACIÓNBACKTRACKING

Esencialmente, la idea es encontrar la mejor combinación posible en un momento determinado, por eso, se dice que este tipo de algoritmo es una búsqueda en profundidad.

Normalmente, se suele implementar este tipo de algoritmos como un procedimiento recursivo.

La diferencia con la búsqueda en profundidad es que se suelen diseñar funciones de cota, de forma que no se generen algunos estados si no van a conducir a ninguna solución, o a una solución peor de la que ya se tiene. De esta forma se ahorra espacio en memoria y tiempo de ejecución.

Algunas heurísticas son comúnmente usadas para

acelerar el proceso. Como las variables se pueden procesar en cualquier orden, generalmente es más eficiente intentar ser lo más restrictivo posible con las primeras (esto es, las primeras con menores valores posibles). Este proceso poda el árbol de búsqueda antes de que se tome la decisión y se llame a la subrutina recursiva.

HEURÍSTICASALGORITMO DE BACKTRACKING

EJEMPLOS DE PROBLEMAS COMUNES RESUELTOS USANDO VUELTA ATRÁS

SudokuProblema de los movimientos de

un caballoLas ocho reinas

Algoritmo de Backtracking

Backtracking Recursivo

Backtracking es una técnica algorítmica que consiste en la resolución de problemas mediante la búsqueda sistemática de soluciones exhaustivas. Comúnmente, esta técnica hace uso de la recursividad, y es importante que domines la implementación de las llamadas recursivas con destreza antes de continuar. Te invitamos a que leas el tutorial: Recursividad: La guía definitiva, y aunque no lo consideres necesario puede que te sean útiles algunos consejos que te ayudarán en la formación como programador.