Recursividad 2° parte

Investigando un poco más, viendo de distintos lados, recompilé un poco más sobre recursividad.
De esta manera, utilizo estos posts no solo para compartir conocimientos sino para aprender más.

una funcion recursiva es aquella que se llama asi misma de forma directa o indirecta (a travez de otra funcion)

metodologia:
* una funcion recursiva sabe unicamente como resolver el caso mas sencillo o caso base.
* si se llama a una funcion con un problema mas complejo, esta divide la tarea en dos piezas conceptuales:

1. la pieza que sabe resolver el caso base o problema mas simple.
2. la pieza que no sabe como resolver el problema..

para que la recursividad se de la pieza 2 debe llamar a un problema (funcion) similar al original pero una vesion mas simple de esta (mas facil de resolver).

* como la pieza 2 representa una version similar al problema original, esta va llamar (cuantas veces sea necesario) a una nueva copia del problema cada vez mas pequeño o simple (la funcion se llama asi misma). a esto se le conoce como paso recursivo

* para que la recursividad acabe, esta serie de problemas cada vez mas pequeños o mas sencillos debe converger en el caso baso. cuando sucede esto la funcion ya sabe como resolver el problema y en este punto se genera una serie de retornos hasta llegar a la funcion original y devuelve el resultado final a la funcion que la llamo (por lo general main()).

por lo general las funciones recursivas tienen una estructura similar a esto

void funcionRecursiva (<tipo>valor)
{
   if (evaluacion) // evalua el caso base      ---> pieza 1
   return 1; // (por ejemplo) caso base.
  else //paso recursivo
  return valor*funcionRecursiva (valor-1); // observa que el problema se hace mas sencillo (valor-1)
}

te pongo un ejemplo (elevar un numero a una potencia)

//Ejercicio de Recursividad.
# include <iostream>

using namespace std;
long int potencia (int,int);
int main ()
{
    int base,exponente;
    cout<<"\n\t programa Potencia";
    cout<<"\n escriba el numero a elevar: \n";
    cin>>base;
    cout<<" elevado a ";
    cin>>exponente;
    cout<<"\n Resultado: "<<potencia(base,exponente);
    return 0;
}

long int potencia (int b, int e)
{
    if (e==1) //pieza 1
    {
        return b; //caso base
    }
    else //pieza 2
    {
        return b*potencia(b,e-1); //paso recursivo
    }
}

La recursividad si responde a la logica de las funciones. Pero que pasa, cada vez que haces un llamado a la funcion se crean en memorias nuevas variables locales y argumentos. 

En ese ejemplo de potencia, supone que llamamos asi:
potencia(4,3);

En el primer llamado a la funcion e no es igual a uno por lo que el if pasa al else. Ahi se va a calcular 4 * potencia(4,3-1); Para calcular ese numero, se realiza un nuevo llamado a la funcion potencia que es totalmente aparte del anterior. Ahora los argumentos esta vez son 4 y 2.

De nuevo e no es igual a uno, por lo que se re quiere calcular 4 * potencia(4,1). Se hace un llamado nuevamente a potencia, completamente distitno a los otros dos, y ahora si e es igual a uno por lo que se devuelve 4.

En el segundo llamado tenias que calcuar 4 * potencia(4,1) = 4 * 4 = 16. Entonces devolvemos 16. Y llegamos al primner llamado en donde debiamos calcular 
4 * potencia(4,2) = 4 * 16 = 64
Y ese es el resultado de la funcion.

Un desarrollo mas matemtico seria:

potencia(4,3) = 4 * potencia(4,2) = 4 * 4 * potencia(4,1) = 4 * 4 * 4 = 4 * 16 = 64

el caso base sirve para evitar la recursion infinita..

la funcion "piensa asi".. si exponente es igual a 1 entonces no tengo que hacer nada solo devuelvo la base porque a^1=a. sino entonces multiplica la base por la base^e-1 porque es lo mismo tener 3^3 que tener 3*3^2 o 3*3*3^1...

osea si tienes base=2 y exponente =3. la funcion no entra en el if porque la evaluacion es falsa ya que exponente no es igual a 1. entonces va a multiplicar 2*2^2.. luego 2*2*2^1 y en este caso la funcion reconoce el caso base y devuelve 2.. apartir de aqui se producen una serie de retornos.. la ultima funcion llamada devuelve 2, la que le sigue devuelve 2*2 y la primera (la original) devuelve a main 2*2*2.

Si en el main llamas a una funcion cualquiera, y desde ella pones un return, vas volves al main.
Ahora si desde una funcion f llamas a la funcion f nuevamente, al poner un return desde la funcion f vas a volver a la funcon f pero desde donde fue llamado.

Para entender un poco mejor eso te recomiendo que imprimas en pantalla y vas a poder seguir la ruta:


Código C++:



long int potencia (int b, int e)
{
     long int temporal;    
     cout << e;
    if (e==1) //pieza 1
    {
        return b; //caso base
    }
    else //pieza 2
    {
              cout << "llamo a potencia con" << b << " y " << e -1;
              temporal = potencia(b,e-1);    
              return b*temporal; //paso recursivo
    }
}




Ya no se como explicartelo. Los dos return son alcanzados. Cada uno en diferentes llamadas al a funcion potencia.

Lo que no estas entendiendo es que cuando volves a llamar a la funcion potencia, osea haces el llamado recursivo, todas las variables locales y todo el entorno de la funcion es duplicado y se crea un nuevo llamado, preservando en memoria el anterior. Asi que cuando este nuevo llamado hace el return, osea, vuelve el valor, este llega al primer llamado de la funcion se realizan las cuentas y se vuevle a retornar un valor mas actualizado.




Creo que el problema esta en entender como funciona el registro de activación (RA) y el paso de parametros reales a parametros formales.
En este caso concreto, suponiendo que le demos a la base el valor 2 y exponente 3. Cuando tu das los parametros (reales) en el main ( ) estos quedan almacenados en el registro de activacion del main durante todo el proceso como b==2 y e==3 . En canvio en la función potencia ocurre otra cosa:


1- El if no se ejecuta ya que e!=1 por lo que se la salta y se ejecutan las instrucciones del else con los 
parametros reales que se le pasan desde el main ( ) b==2 y e== 3.
La funcion potencia crea su propio RA en el que b ==2*2 y e==2.

2- Como sigue sin cumplirse el if se vuelve a ejecutar el else pero esta vez los parmetros reales que se
le pasan a potencia son b=2*2 e==2 y despues se destruye el RA de la función.
Ahora el nuevo RA de potencia valdra b=2*2*2 y e==1.
3- Ahora el if se cumple y el preprocesador le devuelve el control al main ( ) con el valor b==6.


Si no me equivoco el tema funciona así. Espero que te sirva de ayuda.