Recursividad

Eficacia de la recursividad:

Se dice que es menos eficaz que la iterativa porque ocupa más memoria y mayor tiempo de ejecución pero hace el programa más sencillo y comprensible. Un programa recursivo se puede transformar en una solución iterativa mediante el uso de pilas.

TIPOS DE RECURSIVIDAD

1. Recursividad Simple:

en cuya definición sólo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iterativos.

2. Recursividad Múltiple:

Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más difícil de hacer de forma iterativa.

int Fib( int n ) /* ej: Fibonacci */

{ if(n<=1) return(1);

return(Fib(n-1) + Fib(n-2)); }

3. Recursividad Anidada:

Algunos de los argumentos de la llamada recursiva hay una nueva llamada a sí misma.

int Ack( int n, int m ) /* ej: Ackerman */

{ if(n==0 ) return(m+1);

else if(m==0) return(Ack(n-1,1));

return(Ack(n-1, Ack(n,m-1)));

}

4. La recursividad directa

Este tipo de recursividad se muestra en aquellas funciones que se invocan asi mismas.

Cadenas recursivas:

Una función recursiva no necesita llamarse a sí misma de manera directa, puede hacerlo de manera indirecta.

Es decir una función a llama a b, la cual puede a su vez llamar a a, que puede llamar de nuevo a b. Así, ambas funciones a y b, son recursivas, dado que se llamas a sí mismo de manera indirecta.

Definición recursiva de expresiones algebraicas:

a. una expresión es un término seguido por un signo mas seguido por un término, o un término solo

b. un término es un factor seguido por un asterisco seguido por un factor, o un factor solo.

c. Un factor es una letra o una expresión encerrada entre paréntesis.

Ninguno de los tres elementos anteriores está definido en forma directa en sus propios términos.

Cada uno de ellos se define de responsables del reconocimiento de factores y término, respectivamente. También reinicializan pos en la posición que sigue al factor o término de mayor longitud que se encuentra en la cadena str.

Los códigos para estas rutinas se apegan bastantes a las definiciones dadas antes. Cada una intenta satisfacer uno de los criterios para la entidad que se reconoce. Si se satisface uno de esos criterios el resultado es TRUE (VERDADERO). Si no satisface ninguno, el resultado es FALSE (FALSO).

Programación Recursiva:

Cuando escribimos un programa para resolver un problema no hay razón para buscar una solución recursiva. La mayoría de los problemas pueden resolverse de una manera directa usando métodos no recursivos. Sin embargo, otros pueden resolverse de una manera mas lógica y elegante mediante la recursión.

El factor es, probablemente,

...