Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Recursividad II




Enviado por Pablo Turmero



    Monografias.com
    Se dice que algo es recursivo si se define en función de
    sí mismo o a sí mismo. El caso es que las
    definiciones recursivas aparecen con frecuencia en
    matemáticas, e incluso en la vida real. Un ejemplo: basta
    con apuntar una cámara al monitor que muestra la imagen
    que muestra esa cámara. En matemáticas, tenemos
    múltiples definiciones recursivas: – Números
    naturales:   (1) 1 es número natural.  (2) el
    siguiente número de un número natural es un
    número natural – El factorial: n!, de un número
    natural (incluido el 0):   (1) si n = 0 entonces: 0! =
    1  (2) si n > 0 entonces: n! = n · (n-1)!

    Monografias.com
    Asimismo, puede definirse un programa en términos
    recursivos, como una serie de pasos básicos, o paso base
    (también conocido como condición de parada), y un
    paso recursivo, donde vuelve a llamarse al programa. En un
    computador, esta serie de pasos recursivos debe ser finita,
    terminando con un paso base. Es decir, a cada paso recursivo se
    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. Ni el paso base ni el paso recursivo
    son necesariamente únicos.

    Monografias.com
    Por otra parte, la recursividad también puede ser
    indirecta, si tenemos un procedimiento P que llama a otro Q y
    éste a su vez llama a P. También en estos casos
    debe haber una condición de parada. Existen ciertas
    estructuras cuya definición es recursiva, tales como los
    árboles, y los algoritmos que utilizan árboles
    suelen ser en general recursivos. A continuación se expone
    un ejemplo de programa que utiliza recursión indirecta, y
    nos dice si un número es par o impar. Al igual que el
    programa anterior, hay otro método mucho más
    sencillo de determinar si un número es par o impar, basta
    con determinar el resto de la división entre dos. x

    Monografias.com
    Por ejemplo: si hacemos par(2) devuelve 1 (cierto). Si hacemos
    impar(4) devuelve 0 (falso). /* declaración de funciones,
    para evitar errores */ int par(int n); int impar(int n); int
    par(int n){ if (n == 0) return 1; return impar(n-1); } int
    impar(int n){ if (n == 0) return 0; return par(n-1); }

    Monografias.com
    ¿Qué pasa si se hace una llamada recursiva que no
    termina? Cada llamada recursiva almacena los parámetros
    que se pasaron al procedimiento, y otras variables necesarias
    para el correcto funcionamiento del programa. Por lo tanto si se
    produce una llamada recursiva infinita, esto es, que no termina
    nunca, llega un momento en que no quedará memoria para
    almacenar más datos, y en ese momento se abortará
    la ejecución del programa. Para probar esto se puede
    intentar hacer esta llamada en el programa factorial definido
    anteriormente: factorial(-1);

    Monografias.com
    ¿Cuándo utilizar la recursión? Para empezar,
    algunos lenguajes de programación no admiten el uso de
    recursividad, como por ejemplo el ensamblador o el FORTRAN. Es
    obvio que en ese caso se requerirá una solución no
    recursiva (iterativa). Tampoco se debe utilizar cuando la
    solución iterativa sea clara a simple vista. Sin embargo,
    en otros casos, obtener una solución iterativa es mucho
    más complicado que una solución recursiva, y es
    entonces cuando se puede plantear la duda de si merece la pena
    transformar la solución recursiva en otra iterativa.
    Posteriormente se explicará como eliminar la
    recursión, y se basa en almacenar en una pila los valores
    de las variables locales que haya para un procedimiento en cada
    llamada recursiva. Esto reduce la claridad del programa.
    Aún así, hay que considerar que el compilador
    transformará la solución recursiva en una
    iterativa, utilizando una pila, para cuando compile al
    código del computador.

    Monografias.com
    Ejercicio La famosa sucesión de Fibonacci puede definirse
    en términos de recurrencia de la siguiente manera: Fib(1)
    = 1 ; Fib(0) = 0 Fib(n) = Fib(n-1) + Fib(n-2); si n >= 2
    ¿Cuantas llamadas recursivas se producen para Fib(6)?.
    Codificar un programa que calcule Fib(n) de forma recursiva.
    Nota: no utilizar estructuras de datos, puesto que no queremos
    almacenar los números de Fibonacci anteriores a n;
    sí se permiten variables auxiliares.

    Monografias.com
    Dados dos números a (número entero) y b
    (número natural mayor o igual que cero) determinar a^b.
    int potencia(int a, int b){ if (b == 0) return 1; else return a *
    potencia(a, b-1); } La condición de parada se cumple
    cuando el exponente es cero. Por ejemplo, la evaluación de
    potencia(-2, 3) es: potencia(-2, 3) -> (-2) ·
    potencia(-2, 2) -> (-2) · (-2) · potencia(-2, 1)
    -> (-2) · (-2) · (-2) · potencia(-2, 0)
    -> (-2) · (-2) · (-2) · 1

    Monografias.com
    Dado un array constituido de números enteros y que
    contiene N elementos siendo N >= 1, devolver la suma de todos
    los elementos. int sumarray(int num[ ], int pos, int N){ if (pos
    == N-1) return num[pos]; else return num[pos] + sumarray(num,
    pos+1, N); }… int num[5] = {2,0,-1,1,3}; int N = 5;
    printf("%dn",sumarray(num, 0, N));

    Monografias.com
    Dado un array constituido de números enteros, devolver la
    suma de todos los elementos. En este caso se desconoce el
    número de elementos. En cualquier caso se garantiza que el
    último elemento del array es -1, número que no
    aparecerá en ninguna otra posición. int
    sumarray(int num[], int pos){ if (num[pos] == -1) return 0; else
    return num[pos] + sumarray(num, pos+1); } … int num[5] =
    {2,4,1,-3,1}; printf("%dn",sumarray(num, 0));

    Monografias.com
    Dado un array constituido de números enteros y que
    contiene N elementos siendo N >= 1, devolver el elemento
    mayor. int mayor(int num[], int pos){ int aux; if (pos == 0)
    return num[pos]; else { aux = mayor(num, pos-1); if (num[pos]
    > aux) return num[pos]; else return aux; } }… int num[5] =
    {2,4,1,-3,-1}; int N = 5; printf("%dn", mayor(num, 4));

    Monografias.com
    1) Dado un array constituido de números enteros y que
    contiene N elementos siendo N >= 1, devolver el elemento
    mayor. En este caso escribir un procedimiento, es decir, que el
    elemento mayor devuelto sea una variable que se pasa por
    referencia. 2) La función de Ackermann, siendo n y m
    números naturales, se define de la siguiente manera:
    Ackermann(0, n) = n + 1Ackermann(m, 0) = A(m-1, 1)Ackermann(m, n)
    = A(m-1, A(m, n-1)) 3) Dado un array constituido de
    números enteros y que contiene N elementos siendo N >=
    1, escribir una función que devuelva la suma de todos los
    elementos mayores que el último elemento del array. 4)
    Dado un array constituido de números enteros y que
    contiene N elementos siendo N >= 1, escribir una
    función que devuelva cierto si la suma de la primera mitad
    de los enteros del array es igual a la suma de la segunda mitad
    de los enteros del array.

    Monografias.com
    El Problema Fue presentado en 1883 por el matemático
    francés Edouard Lucas (1842 – 1891). El problema
    consistía en lo siguiente: hay que mover una torre,
    compuesta de discos de diferentes tamaños, de una aguja a
    otra. Sólo hay dos reglas: Sólo se puede mover un
    disco a la vez No está permitido mover un disco encima de
    otro más pequeño

    Monografias.com
    Según Lucas el juego había sido rescatado por el
    Profesor N. Claus de Siam. La leyenda contaba que en el templo de
    Benarés, Dios colocó durante la creación 64
    anillos en una aguja. Desde entonces los bramanes, durante
    incontables generaciones, han estado moviendo los discos de
    acuerdo con las reglas de arriba. Cuando hayan conseguido mover
    todos los discos, el templo se derrumbará y el mundo se
    desvanecerá.

    Monografias.com
    La solución Para resolver esto, empezamos por supuesto con
    algo más fácil y lo más fácil que hay
    es una torre compuesta por un único anillo.
    ¿Cuántos movimientos necesitamos? Evidentemente uno
    solo.

    Monografias.com
    ¿Y con 3 discos?

    Monografias.com
    void hanoi(int n,int com, int aux, int fin){ if(n==1) printf("%c
    -> %c",com,fin); else{ hanoi(n-1,com,fin,aux); printf("n%c
    -> %cn",com,fin); hanoi(n-1,aux,com,fin); } }

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter