Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

RECURSIÓN Y LISTAS SIMPLES RECURSIVAS

No description
by

Gabriel Chaldu

on 26 September 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of RECURSIÓN Y LISTAS SIMPLES RECURSIVAS

Ejemplo: Imprimir un Arreglo (iterativo)
Reglas de la buena recursión
void imprimirArreglo(int arreglo[], int validos)
{
int i=0;

while
(i<validos)
{
printf("Datos: %d\n", arreglo[i]);
i++;
}
}
Toda función recursiva debe tener:
Recursividad Indirecta
Recursividad Directa
El programa o subprograma se llama directamente a sí mismo.
RECURSIVIDAD
Una función se dice recursiva si durante su ejecución se invoca
directa
o
indirectamente
a sí mismo.

¿Cuando un función es recursiva?
int
sumaRecursiva(
int arreglo[ ]
,
int validos
,
int i
)
{
int
rta
;
if (
i

==

validos
)
{

rta
=

0
;

}else
{

rta
=
arreglo[
i
]

+

sumaRecursiva(
arreglo
,
validos
,
i+1
);
}
return
rta
;
}
Ejemplo
Recursividad y Lenguaje C
Acercamiento a la Condición de corte
Llamada Recursiva
El subprograma llama a otro subprograma, y éste, en algún momento, llama nuevamente al primero.
Ejemplo
int impar (int num)
{
if (num==0)
{
return 0;
}else
{
return
par(num-1);
}
}

int
par (int num)
{
if (num==0)
{
return 1;
}else
{
return
impar(num-1);
}
}
El numero uno pertenece a los Naturales, y si N pertenece a los Naturales, N+1 también.
Ej: Factorial de 5! = 1*2*3*4*5 = 120
Factorial(0) = 1 (
solución trivial
)
Factorial(N) = N * Factorial(N-1), para todo N > 0.
0 ! = 1
N ! = N * (N - 1) !
Parece un concepto nuevo, pero ya lo hemos visto en
varias definiciones matemáticas…
... pensemos en el factorial del numero 1
Desarrollo de la funcion factorial
int
factorial
(
int
x)
{
int
rta;
if ( x = = 0)
rta = 1;
else
rta = x *
factorial
(x-1) ;
return
rta;
}
Paso a paso... calculemos el factorial de 3
¿Como funciona esto?
En el momento de realizar una invocación recursiva,
se suspende la ejecución de la función invocante hasta que se termina de resolver la función invocada
.

Si bien es la misma función la que se invoca,
se genera un nuevo espacio de memoria para la resolución de la misma
.

Cada espacio tiene sus propias variables locales y parámetros, con valores propios
.
Ejemplo: Imprimir un Arreglo
void muestraArregloRecursivo(int A[], int i, int cant)
{
// condición de corte explicita
if(i==cant-1)
printf(" %d", A[i]);
else
{
printf(" %d", A[i]);
muestraArregloRecursivo(A, i+1, cant);
}
}
Ejemplo: Imprimir un Arreglo
int main()
{
if (
par(3)==1
)
{
printf("\nEs Par");
}else
{
printf("\nEs IMPar");
}
}
Prof. Gabriel Chaldu
Prof. Gustavo Sonvico

int main ()
{
int unArreglo[10];

int validos = cargarArreglo(unArreglo, 10);

int suma = sumaRecursiva(unArreglo, validos, 0);




printf("La suma del contenido del arreglo es %d", suma);

return 0;
}
// cargamos el arreglo
// le pasamos el arreglo, la cantidad de elementos validos y un 0 (cero), que le indica a la función desde donde tiene que comenzar a trabajar
Relación entre Recursión e Iteración
Recursion vs. Iteración
¿Cuál de los dos métodos debería ser usado para resolver un problema dado?

Una solución recursiva
el computador
debe controlar y resolver
cada una de
las invocaciones
manteniendo información acerca del resultado las mismas.
Esto puede ser costoso en tiempo y espacio.

Se recomienda el uso de una solución recursiva sólo en caso que:
L
a solución no puede ser fácilmente expresable iterativamente
.
La eficiencia
de la solución
recursiva es satisfactoria.
Función recursiva de Factorial
Listas con recursión
La lista, en la definición de su estructura, ya nos demuestra que
se trata de una estructura de datos recursiva
.
typedef

struct nodo
{
int dato;

struct nodo
* siguiente;
};
Una lista que apunta a NULL es una Lista.... y además, un Nodo seguido de una Lista
también es una Lista.
Consideremos que, cuando llamamos a una función recursiva vamos a trabajar con una lista... y en los siguientes espacios que genera la llamada recursiva, también vamos a trabajar con una lista... que es una sublista de la lista principal. Así, hasta llegar a NULL.
Ejemplo: recorrer una lista vinculada
void
recorrerYmostrar
(nodo * lista) {
if(lista!=NULL)
{
printf("%d ", lista->dato);
recorrerYmostrar
(lista->siguiente);
}
}
Condición de Corte
(corta cuando es NULL)
Acercamiento a la Condición de Corte
Llamada recursiva
Solución Trivial (implícita): ausencia de ELSE.
No hace nada al llegar a NULL
Podremos ver que la lista se trabaja de forma mas sencilla utilizando funciones recursiva...
Ejemplo: sumar el contenido de una lista de enteros.
Para solucionar este problema planteo el siguiente algoritmo:

“La suma de una lista vacía es 0”
“La suma de los números de una lista será igual a la suma entre el primero y el resultado de la suma de la sublista siguiente.”

En este caso particular del ejemplo de la lista, se separa el primer elemento y se supone conocida la solución de los restantes.

También se le llama “separarlo en cabeza y cola”.
int
suma
(nodo * lista)
{
int rta;
if(lista == NULL)
// “La suma de una lista vacía es 0”
rta = 0;
else
rta = lista->dato
+
suma
(
lista->siguiente
);
/* “La suma de los números de una lista será igual a la
suma entre el primero y el resultado de la suma de la
sublista siguiente.” */
return rta;
}
cabeza
cola
¿Cual es la diferencia?
void
recorrerYmostrar
(nodo * lista) {
if(lista!=NULL)
{
printf("%d ", lista->dato);
recorrerYmostrar
(lista->siguiente);
}
}
void
recorrerYmostrar
(nodo * lista)
{
nodo * seg = lista;
while (seg != NULL)
{
printf("edad: %d \n\n", seg->edad);
seg= seg->siguiente;
}
}

Al menos
una Llamada Recursiva
(o Entrada en Recursión).
En cada Llamada Recursiva, se produce
un acercamiento a la Condición de Corte.
Al llegar a la Solución Trivial, queda expresada la solución total.
Al menos una
Condición de Corte
con su respectiva
Solución Trivial
.
Condición de corte
Solución Trivial
La recursividad
invoca de manera repetida y
puede sobrecargar
tanto
en tiempo de procesador
como
en espacio de memoria
.
La iteración
utiliza una estructura de
repetición
de forma explícita;
la recursión
consigue
la repetición
mediante llamadas de función repetidas.
La iteración
termina cuando
falla la condición
de continuación del ciclo;
la recursión
termina cuando se produce la
condición de corte
es verdadera.
La iteración
se puede quedar en un
bucle infinito
si la condición del ciclo nunca se hace falsa;
la recursión
se hará infinita
si no hay acercamiento a la condición de corte
que converja al caso base.
La
iteración
utiliza una
estructura de repetición
y
la recursión
una
estructura de selección
.
Repetición infinita:
Terminación:
La repetición:
La estructura:
Un problema recursivo:
Hay variable seguidora (seg)
Estructura repetitiva
+
Condición de salida
Estructura condicional
+
Llamada recursiva
Acercamiento
Asignación
Full transcript