Rcursividad en ANSI C

[Betops]

Hola a todos, antes que nada me presento, soy Betops, y usualmente andaba foreando por la parte de hardware, y resulta que ahora estoy estudiando programacion en la facu y llegamos al tema de recursividad en ANSI C... y lo cierto es que no lo entiendo, no puedo captar el pensamiento recursivo.
Quisiera saber si alguno de ustedes podria pasarme links o bibliografias que me ayuden a comprender como abordar ejercicios desde el punto de vista recursivo...
Viendo en las clases de programacion II me di cuenta que muchos algoritmos iterativos se pueden simplificar en forma recursiva, asi que estoy interesado en comprender este tema que se que es dificil pero tengo ganas de aprenderlo porque he visto lo util que resulta dominarlo.
Desde ya muchisimas gracias a todos.

Saludos:

§_Betops_§

[Instru]

Pues es sencillo, ahora te doy una explicacion resumida.

Pero primero, te digo que lo que dices:

muchos algoritmos iterativos se pueden simplificar en forma recursiva

Desde mi punto personal de vista yo creo que es al revés. Muchos algoritmos en forma recursiva se simplifican en forma iterativas. Ya que como tu lo has notado, es mucho mas dificil leer y entender una recursividad que una estructura de iteracion(for, while, do...)

La recursividad, como ya has de saber, es cuando una funcion se llama a si misma.
Lo que te rompe la cabeza es pensar. "Si se llama a si, cuando carajos termina!!!"
Pues eh ahi la respuesta.

Para que una funcion sea recursiva, tienene forzosamente que tener una condifion(if) donde le digas hasta que profundidad debe llegar.

El caso que abordan tooodoos(o casi todos) los libros, maestros, etc, es el del factorial.

El factorial es por ejemplo:
9!= 9*8*7*6*5*4*3*2*1
Obviamente esto lo puedes hacer con un ciclo for, while o el que se te ocurra.
Pero se aplica muy bien para demostrar la recursividad.

Primero tienes una funcion:

int funcion(int factorial)
{
}

Obviamente debe regresar un valor, para poder trabajar con este valor dentro de ella misma.

int(funcion(int numero)
{
if(numero==0)
return 1;
else
return numero*funcion(numero-1);
}

Como veras, el factorial lo terminas de calcular al llegar al 1.
Entonces, debes decirle.
Si numero es cero, YA NO VUELVES A LLAMAR ALA FUNCION solo regresas 1.
Entonces, empeizas a salir del remolino de llamadas a la funcion.
Y en cada salida, te va regresando parte del resultado que se multiplica por el numero mas grande y asi sucesivamente.

Si no me entendiste, hay otro post por ahi, donde lo explican mucho mas claro.

Saludos

[moyka]

Iniciado por Instru

int(funcion(int numero)
{
if(numero==0)
return 1;
else
return numero*funcion(numero-1);
}

Hola,
hombre en ese caso no haría falta llegar hasta cero, al llegar a 1 ya puedes parar la recursión.

Otro buen ejemplo puede ser el de realizar una potencia de un número de forma recursiva, lo más importante en la recursividad es encontrar el caso base, una vez encontrado (como en el ejemplo anterior del factorial), todo va ya sobre ruedas.


En el ejemplo de la potencia de un número, el caso base es cuando el exponente es 1, todo número elevado a 1 es igual a dicho número, así que en esta función, decrementaremos el exponente en una unidad hasta llegar a uno.

Lo único que resta para tener la función completa es ver el número con el que operar en la llamada recursiva, es decir, en este caso multiplicaremos cada llamada recursiva por el número a elevar.

Sería así:

Código:

int elevar(int base,int exponente){
    if(exponente == 1)
       return 1;
    return (elevar(base,exponente-1)*base);
}

Espero haberte ayudado un poco, si necesitas más ejemplos mándame un privado.
Un saludo.

[_Lucifer_]

Iniciado por moyka

Hola,
hombre en ese caso no haría falta llegar hasta cero, al llegar a 1 ya puedes parar la recursión.

Otro buen ejemplo puede ser el de realizar una potencia de un número de forma recursiva, lo más importante en la recursividad es encontrar el caso base, una vez encontrado (como en el ejemplo anterior del factorial), todo va ya sobre ruedas.


En el ejemplo de la potencia de un número, el caso base es cuando el exponente es 1, todo número elevado a 1 es igual a dicho número, así que en esta función, decrementaremos el exponente en una unidad hasta llegar a uno.

Lo único que resta para tener la función completa es ver el número con el que operar en la llamada recursiva, es decir, en este caso multiplicaremos cada llamada recursiva por el número a elevar.

Sería así:

Código:

int elevar(int base,int exponente){
    if(exponente == 1)
       return 1;
    return (elevar(base,exponente-1)*base);
}

Espero haberte ayudado un poco, si necesitas más ejemplos mándame un privado.
Un saludo.

Una correccíon:

Código:

int elevar(int base,int exponente){
    if(exponente == 0)
       return 1;
    return (elevar(base,exponente-1)*base);
}

Si quieres llegarlo hasta 1 sería:

Código:

int elevar(int base,int exponente){
    if(exponente == 1)
       return base;
    return (elevar(base,exponente-1)*base);
}

Cualquier número elevado a la 1 es el mismo número y cualquier número elevado a la 0 es 1.

Saludos