Ayuda c++ Recursividad.

(Semaforo rojo) No supera els jocs de proves!

Es muy sencillo, como (si no recuerdo mal, y de ahí la primera frase de este post) creo k es un ejercicio de P1 de la FIB, y hay otras variantes, este te lo resuelvo para k intentes entenderlo:

La cosa es girar una secuencia de palabras (diria que este ya lo dije en este foro :/).
Explicado en plan PRAP puedes decir que SI lees, por HI has escrito el resto de palabras a la inversa (al realizar la llamada recursiva) y, finalmente, escribes la palabra actual.

void gira() {
string palabra;
if (cin >> palabra) {
gira();
cout << palabra << endl;
}
}

int main() {
gira();
}

Pero lo puedes pensar de forma menos estricta viendo fácilmente:
Si se lee una palabra la guarda en memoria y realiza una llamada recursiva (guardando otra palabra).
Si en una llamada no lee se acaba la recursión (no entra en el IF) y terminará la anterior llamada, es decir, la que ha guardado la última palabra (escribe ultima), y así sucesivamente (escribe penultima, .... primera)

Y la explicación de la recursividad es que realmente no tiene mucha, simplemente se vuelve a llamar a la misma función para aplicar el mismo tratamiento sobre los elementos restantes. La cosa está en tener un caso base (en el ejemplo anterior el caso base es "cuando no se lee") que sea "sencillo" y su resultado esté bien definido.

Ejemplo típico el del factorial de un número.

5! = 54321

Pero también está la definición recursiva:

5! = 5*4!

Como ves es el número actual N por el factorial de N - 1

¿Caso base? El factorial de 0 es 1 (o puedes decir que menor de 2 es 1, ya que factorial de 0 y de 1 son iguales, pero bueno):

int factorial (int n) {
// Caso base
if (n == 0) return 1; <--- Caso base resuelto (lo que decía del 2 es que puedes poner "if (n < 2)")
return nfactorial(n - 1); <--- else = n(n-1)!
}

¿Porque funciona? Porque están bien definido el caso base y el caso recursivo:

el factorial de 0 es 1
el factorial de n (n != 0) es n * (n - 1)!

Y un último ejemplo que te tienen que haber enseñado en clase es la ordenación por fusión (merge sort):

void merge_sort(vector< int>& v, int inicio, int fin) {
if (inicio < fin) {
int medio = (inicio + fin)/2;
merge_sort(v, inicio, medio); // <-- Ordena la parte izquierda
merge_sort(v, medio + 1, fin); // <-- Ordena la parte derecha
fusiona...
}
}

Como ves también está declarada recursivamente. Ordena priemro la parte izquierda, después ordena la parte derecha y, finalmente, fusiona ambas partes.

¿Caso base? Si "inicio == fin" es un sub-vector de 1 solo elemento, al ser solo 1 elemento es obvio que está ordenado (ordena una baraja de cartas que solo tiene 1 carta, ya está ordenada puesto que no hay más cartas). Así que por HI tienes la parte izquierda y derecha ordenadas y solo te falta fusionarlas entre si.

"Si me pudierais explicar tmbien como funciona un poco la recursividad"

Una función recursiva es una función que se llama así misma. Algo así:

funcionRecursiva
&nbsp;me&nbsp;llamo&nbsp;a&nbsp;mi&nbsp;misma--->funcionRecursiva
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;me&nbsp;llamo&nbsp;a&nbsp;mi&nbsp;misma---->funcionRecursiva
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;me&nbsp;llamo&nbsp;a&nbsp;mi&nbsp;misma---->funcionRecursiva

Para evitar un cadena infinita en la que la función se llama así misma sin parar, la llamada a sí misma, está siempre dentro de una condición. Se supone que en algún momento la condición no se cumplira, entonces la última llamada a la función termina sin que la funció se llame así misma otra vez, y se va retornando a las llamadas anteriores de la función. Algo así

La recursividad es una variante de los bucles, cualquier problema recursivo se puede resolver con bucles.

Todas las llamadas a las funciones usan la pila, aunque sea una función llamandose así misma, y está claro que las llamdas de la función así misma van retornando desde la última a la primera.

De todas formas eso no te afecta en nada, es un proceso transparente.

#8, los ordenadores son iterativos, si haces una función recursiva, el compilador/intérprete te lo pasa a iterativo.

Que es jodido hacerlo a mano, si, pero todo se puede hacer con bucles

#9 Que están capacitados para realizar esa tarea si, pero que siempre lo hagan no.

Un computador puede realizar sin problema alguno llamadas recursivas puesto que no es más que llamar a la función (algo que el computador sabe hacer) y retornar el resultado