Memoria dinamica recursividad

1. RECURSIVIDAD

( DEFINICIÓN

Recursión, recursividad o recurrencia es la forma en la cual se especifica un proceso basado en su propia definición.
Por ejemplo, el acrónimo GNU significa GNU is Not Unix y el acrónimo PHP significa PHP Hypertext Preprocessor.
Esto permite establecer instancias complejas de un proceso en términos de instancias más simples y de una o másinstancias finales definidas explícitamente.
Un algoritmo recursivo es aquel que expresa la solución de un problema en términos de sí mismo y de una solución simple conocida; ésta, es una referencia que permite completar la solución en una cantidad finita de pasos.
Los algoritmos recursivos pueden adoptar la forma de funciones que retornan un valor o que causan un efecto.

( EJEMPLOSLas funciones solicitadas se implementan en lenguaje C.

( El Terminal de un número entero no negativo n se define mediante la recurrencia
0 si n=0
n¡ =
n + (n(1)¡ si n>0

Implementar la función recursiva suma(n).
int suma(int n)
{ if (n==0)
return 0;
else
return n+ suma(n-1);
}

suma(5)
5 + suma(4)
5 + 4 + suma(3)
5 + 4 + 3 + suma(2)
5 + 4 + 3 + 2+ suma(1)
5 + 4 + 3 + 2+ 1 + suma(0)
5 + 4 + 3 + 2+ 1 + 0
5 + 4 + 3 + 2+ 1
5 + 4 + 3 + 3
5 + 4 + 6
5 + 10
15

( El Factorial de un número entero no negativo n se define mediantela recurrencia
1 si n=0
n! =
n*(n(1)! si n>0

Implementar la función recursiva factorial(n).
int factorial(int n)
{ if (n==0)
return 1;
else
return n*factorial(n-1);
}

( Con respecto a un vector v de valores enteros, implementar la función recursiva printvec(v,n) que despliega los n elementos de v, según un orden ascendente de sus índices.
typedef int vector[100];
void printvec(vector v, int n) // 1 ( n ( 100
{ if (n>0)
{ printvec(v, n(1);
printf("%d", v[n-1]);
}
}

( Implementar la función recursiva binario(n) que imprime los dígitos de la representación binaria de unnúmero natural n.
void binario(int n)
{ int d;
if(n>0)
{ d = n%10;
binario(n/10);
printf(“%d”, d);
}
}

( El n–ésimo número de la sucesión de Fibonacci (orden 1) se define mediante la recurrencia
0 si n=0
Fn = 1 si n=1
Fn-1 + Fn-2 si n>1Implementar la función recursiva fibo(n).
int fibo(int n)
{ if (n==0)
return 0;
else
if(n==1)
return 1;
else
return fibo(n-1) + fibo(n-2);
}
2. LISTAS ENLAZADAS

( DEFINICIÓN

Una lista enlazada es:

( Un objeto vacío.
( Ó, un nodo ligado a unalista enlazada.

( REPRESENTACIÓN

En lenguaje C
typedef struct nodo
{ int dato;
struct nodo *link;
} nodo;
typedef nodo *enlace;

En lenguaje C++
struct Nodo
{ int dato;
Nodo *link;
}
typedef Nodo *Enlace;

( EJEMPLOS

( Implementar una funciónrecursiva que acepte un puntero de acceso a una lista lineal de enlace simple y un valor entero, debiendo almacenar el valor recibido en un nuevo nodo y agregarlo en el "extremo derecho" de la lista. Luego, escribir un "main" que genere una lista utilizando la función implementada.
void agregar(enlace *l, int e)
{ if (*l == NULL)
{ *l = (enlace)malloc(sizeof(nodo));...