viernes, 8 de abril de 2011

Capitulo 10. Recursividad

Fuente:
Programación en C++ / Principios y Aplicaciones (resumen)
Carlos Romero Shollande

1.        Introducción

Un subprograma recursivo es cuando éste se llama a sí mismo, ya sea directa o indirectamente.
La solución recursiva es menos eficiente que la solución iterativa, pero existen numerosas situaciones en las que la recursividad es una solución simple y natural a un problema que en caso contrario sería difícil de resolver.
La mayoría de los subprogramas recursivos no ahorran significativamente memoria y funcionan ligeramente más lento que sus equivalentes iterativos, debido a que consumen mucho espacio de pila y la pueden desbordar. Pues, por cada llamada realizada las variables que intervienen en el subprograma son salvadas en la pila, para poder posteriormente iniciar el retorno.
La comprensión del concepto de recursividad es difícil, por lo que trataremos de explicarla con este ejemplo: Una persona es descendiente del Sr. Ortega si (1) esta persona es un hijo del Sr. Ortega o (2) esta persona es un hijo de un descendiente del Sr. Ortega.
Obsérvese que la palabra “descendiente” se utiliza para definirse a sí misma (descendiente del descendiente).
En la recursividad siempre existe un medio para salir. En el ejemplo anterior, la condición (1) se denomina salida de la definición, y la condición (2) viene a ser la parte recursiva propiamente dicha y que garantiza que siempre se alcance la salida: cuando el descendiente es hijo del Sr. Ortega, se termina el proceso recursivo.

2.        Pilas

La implementación de la recursividad se hace con el uso de una estructura denominada pila (stack). Una pila es un espacio de memoria a la que se accede de un modo especial: el primer elemento en entrar es el último elemento en salir.
Su analogía más clara en la vida ordinaria está en la pila de platos de una cocina. La pila está limitada en espacio por unas direcciones de memoria fijas.
Conceptos fundamentales de una pila: puntero de pila, operación de meter datos en la pila, limpiar la pila o dejar la pila vacía y tamaño o longitud de la pila.

Gráfica 1. Conceptos básicos de una pila


El C++ utiliza al menos una pila durante la ejecución de cualquier programa para almacenar valores de variables, constantes, parámetros y direcciones de retorno.

Gráfica 2. Asignación de espacio en llamadas recursivas:


3.        Funciones Recursivas

La ventaja principal de las funciones recursivas es que se pueden usar para crear versiones más claras y sencillas de los algoritmos que sus correspondientes iterativas.
Por ejemplo, el factorial de un entero no negativo n, que se define como n! (factorial de n), y que fue desarrollado en el problema ilustrativo (2) del capítulo 4 (sentencias repetitivas).
Matemáticamente se expresa como:







Donde 1! es igual a 1 y 0! se define como 1. Mediante la siguiente relación se llega a una definición recursiva de la función factorial.

n! = n * (n-1)!

Por ejemplo, 4! es igual que 4 * 3!, como se demuestra a continuación:

4! = 4 * (4 – 1) * (4 – 2) * (4 – 3) = 4 * 3 * 2 * 1 = 24
4! = 4 * (3 * 2 * 1)
4! = 4 * (3!)

Los subprogramas recursivos deben contener las dos partes o sentencias siguientes:
Una llamada a sí misma (recursiva), normalmente con el valor de los parámetros que cambian en cada llamada.
Una condición de terminación o salida, que es la condición que no produce ninguna autollamada.
En el ejemplo del factorial se tiene:

Llamada recursiva:      n! = n * (n – 1)!

Factorial = n * Factorial (n – 1)

Condición de salida:   n = 0

4.        Procedimientos Recursivos

En el C++ también es posible realizar procedimientos recursivos.
Ejemplo: al obtener el número inverso de un número dado tal como 758, se puede observar que su inverso es 857.
Este se genera invirtiendo las cifras:

n = 758
758 % 10 = 8  r1 = 8   y          758 / 10 = 75
75 % 10 = 5    r2 = 5   y          75 / 10 = 7
7 % 10 = 7      r3 = 7

5.        Seguimiento de la Recursividad

Cuando el subprograma recursivo es invocado por el programa principal u otro subprograma para solucionar algún problema. El subprograma recursivo de hecho sabe cómo resolver los casos más sencillos, los llamados casos base.
Si el subprograma es llamado mediante un caso base, éste simplemente devuelve un resultado.
Si es llamado por un problema más complejo, el subprograma divide al problema en dos partes conceptuales, una parte que dicho subprograma no sabe resolver (proceso de ida) y otra que si sabe resolver (proceso de vuelta).
Para hacer factible la recursión, la primera parte debe parecerse al problema original, pero debe ser ligeramente más sencilla o pequeña que él.
Debido a que este nuevo problema se parece al original, el subprograma llama a una nueva copia de él mismo, que se encargará del problema más pequeño, a esto se conoce como llamada recursiva o paso de recursión.
El paso de recursión también incluye la palabra clave return, pues su resultado se combinará con la parte del problema que el subprograma sabía cómo resolver, formando un resultado que se devolverá al primer invocador, probablemente al programa principal (main).
El paso de recursión se ejecuta mientras la llamada original del subprograma aún está abierta, es decir cuando éste no ha terminado de ejecutarse.
Además puede generar más de tales llamadas recursivas a medida que el subprograma sigue dividiendo, en dos partes, los nuevos subproblemas con los que se llama al subprograma.
Para que la recursión termine, finalmente, cada vez que el subprograma se llame a sí mismo mediante una versión ligeramente más sencilla del problema original, esta secuencia de problemas cada vez más pequeños debe desembocar eventualmente en el caso base.
Le devuelve un resultado a la copia previa de la función y una secuencia de instrucciones return recorre el camino hacia arriba, hasta que la llamada original de la función le devuelve el resultado final a main.
Como ejemplo del funcionamiento de estos conceptos, veamos el problema del factorial en su versión recursiva.
Consideremos el cálculo del factorial para n = 4, enviado como parámetro valor desde otro subprograma o desde el programa principal:

n = 4    Llamada a Factorial(4)  es n = 0;  No
            Factorial = 4 * Factorial(3)
n = 3    Llamada a Factorial(3)  es n = 0;  No
            Factorial = 4 * 3 * Factorial(2)
n = 2    Llamada a Factorial(2)  es n = 0;  No
            Factorial = 4 * 3 * 2 * Factorial(1)
n = 1    Llamada a Factorial(1)  es n = 0;  No
            Factorial = 4 * 3 * 2 * 1 * Factorial(0)
n = 0    Llamada a Factorial(0)  es n = 0;  Si
            Factorial = 4 * 3 * 2 * 1 * 1
            Factorial = 24

No es recomendable declarar a la función factorial como int, ya que cuando n = 8, 8! = 40320, este valor supera ampliamente el rango de los enteros (32767).
Es mejor definirla de tipo long int o de tipo float.
La evaluación del factorial de 4 procede como se muestra en la gráfica siguiente.

Gráfica 3. Seguimiento del algoritmo recursivo Factorial (4!).


En el extremo izquierdo se muestra el proceso de sucesión de llamadas recursivas (proceso de ida) hasta que se evalúa que 0! es igual a 1, con lo que termina la recursión.
En el extremo derecho, se muestran los valores que cada llamada recursiva que los devuelve al invocador, hasta que se calcula y se devuelve el valor final.

6.        Tipos de Recursividad

La recursividad puede ser de dos tipos:
Recursividad directa (simple): un subprograma se llama a sí mismo una o más veces directamente.
Por ejemplo, la función recursiva del factorial.
Recursividad indirecta (mutua): dos o más subprogramas se llaman mutuamente; es decir, un subprograma A llama a otro subprograma B y éste a su vez llama al subprograma A.
Por ejemplo, las funciones recursivas para determinar si un número es par o impar
 
7.        Recomendaciones para el Uso de la Recursividad

Si en un proceso las sucesivas llamadas a un subprograma suponen guardar valores de variables en cada etapa, que posteriormente deben ser procesados en orden inverso, entonces en estos casos es aplicable la recursividad.
La razón es la semejanza con la definición de pila.
Si un proceso se puede definir en términos más simples en función del mismo, como es el caso de sumas, factoriales, etc., se debe preferir el uso de la recursividad.
Si no existe una ventaja clara para utilizar la recursividad, no la utilice.
Por el contrario, si la definición del problema es inherentemente recursiva, entonces la solución recursiva debe ser considerada preferentemente.
Por ejemplo, el problema de las Torres de Hanoi.
Si un algoritmo no recursivo se puede obtener y es menos complejo que el recursivo, mejor usar el no recursivo
Cada llamada recursiva requiere la asignación de espacio de memoria (en la pila) para todas las variables locales, parámetros de valor y la dirección de retorno.
Si cada llamada usa memoria, y si existen limitaciones en memoria central, esto puede suponer una seria limitación.
No utilice la recursividad, a menos que tenga un medio para terminar las llamadas recursivas. Se debe tener la seguridad de que en los datos utilizados existe al menos uno que cumpla con la condición de terminación.
El problema más frecuente con un subprograma recursivo es que puede no terminar adecuadamente.
Por ejemplo, si la condición de terminación no es correcta o incompleta, entonces el subprograma puede producir una recursión infinita o bien llamarse hasta que se gaste toda la memoria disponible.

Ejemplo: 
Usando una función recursiva denominada Factorial(), determinar el factorial de un número ingresado previamente.

Codificación
#include <iostream.h>            // Factorial de un numero

#include <conio.h>
long int factorial(int);
void main()    {
int n;// Número ingresado
int i;                                         // Contador
clrscr();
gotoxy(1,2); cout<<"Ingresar un número: ";
gotoxy(30,2); cin>>n;
cout<<”\n”<<n<<"! = "<<factorial(n)<<"\n";
getch();
}
long int factorial(int n)    {
if(n<=1) return 1;
else return n * factorial(n-1);
}

Capitulo 9. Procedimientos y Funciones

Fuente:
Programación en C++ / Principios y Aplicaciones (resumen)
Carlos Romero Shollande

1.        Introducción

Una estrategia para la solución de problemas complejos reales con computadoras consiste en dividirlos en problemas más pequeños, llamados subproblemas.
Un subproblema puede ser, a su vez, dividido repetidamente en problemas más pequeños, hasta que los problemas más pequeños sean consistentes.
Cada subproblema debe ser independiente de los restantes y se le denomina módulo.
La técnica de dividir un problema en subproblemas se denomina refinamiento sucesivo, diseño descendente o diseño modular, debido a que se comienza en la parte superior de un problema principal y luego se diseñan soluciones especificas para sus subproblemas.

1.1.  Programa Principal

El problema principal se soluciona con un programa denominado programa principal (main), también llamado conductor del programa.
Este programa describe la solución completa del problema y consta de llamadas a subprogramas.
Las llamadas son indicaciones al procesador de que debe continuar la ejecución en el subprograma llamado, regresando al punto de partida una vez haya concluido.
El programa principal puede contener, además, sentencias básicas, selectivas y repetitivas, que son ejecutadas de modo inmediato por el procesador.
El programa principal contendrá pocas líneas, y en el se verán claramente los diferentes pasos del proceso que se han de seguir para la obtención del resultado deseado.

1.2.  Subprogramas

Los subproblemas (módulos) se solucionan mediante declaraciones de subprogramas, ubicados en lugares distintos al del programa principal.
Su estructura coincide básicamente con la de un programa; en consecuencia, un subprograma puede tener sus propios subprogramas.
El objetivo de un subprograma consiste en resolver de modo independiente una parte del problema.
A veces los subprogramas se repiten varias veces en diferentes lugares del programa; en este caso el conjunto de sentencias a repetir aparecerán una sola vez.
Un subprograma es ejecutado sólo cuando es llamado por el programa principal o por otro subprograma.

-       Los subprogramas permiten romper un programa en unidades lógicas discretas, de forma que cada una de ellas puede ser escrita y corregida de un modo más fácil que un programa completo (sin subprogramas), e incluso por programadores diferentes.
-       Los subprogramas utilizados por un programa pueden ser utilizados por otros programas y se pueden crear librerías de funciones y procedimientos.
-       Los subprogramas acortan los programas (si es que el subprograma se utiliza más de una vez), ya que sólo será preciso escribir una sola vez las correspondientes instrucciones, y cada vez que se desea realizar una tarea, el subprograma se encargará de esa operación

Gráfica 1. Diseño descendente del problema principal y programación del programa principal


2.        Variables de los Subprogramas

Al usar subprogramas nos encontramos con cuatro tipos de variables:

2.1.  Variables Locales

En el concepto más amplio, las variables locales son las que se declaran dentro de un bloque de código, y como un subprograma es un bloque discreto de código, se puede concluir que las variables que son locales a un subprograma son simplemente un caso especial del concepto general.
Las variables locales existen sólo durante la ejecución del bloque de código en el que se declaran; es decir, una variable local se crea al entrar en su bloque y se destruye después de salir.
Así las variables locales no son conocidas fuera de su propio bloque de código y no pueden retener sus valores entre llamadas. Ejemplo:

void alfa()      {
            int j;         // j es variable local de alfa()
            j = 77;  }
void beta()      {
            int j;        // j es variable local de beta()
            j = -66; }

La j se declara dos veces, una en alfa() y otra en beta().
La j en alfa() no tiene relación con la j de beta(), ya que cada j es conocida sólo por el código que esta en el bloque que la declaró.
La ventaja de declarar un variable local en un bloque es que se asignará memoria a la variable sólo si es necesario

2.2.  Variables Globales

Las variables globales son las variables que se conocen a través de todo el programa y se pueden usar en cualquier bloque de código.
Se pueden crear variables globales declarándolas fuera de cualquier subprograma.
Un subprograma puede acceder a ellas sin tener en cuenta en que lugar este dicha expresión.
Ejemplo:
#include <iostream.h>
int i;                            // Variable global a todo el programa
void beta()    {
            int i;                 // Variable local a beta()
            for(i=1; i<10; i++) cout<<“ . “;
            }
void alfa()    {
            beta();              // Llamada a beta()
            cout<<“El contador es: “<<i;
            }
main()   {
            i = 230;            alfa();
            }

Aunque ni main(), ni alfa() tienen declarada la variable i, ambas se usan.
Sin embargo, beta() ha declarado una variable local llamada i.
Cuando se referencia i, beta() referencia sólo a su variable local, no a la global.
En conclusión, si una variable local y una global tienen el mismo nombre, todas las referencias a ese nombre de variable, dentro del subprograma en el que se declara como local, se referirá a la local y no afectara a la variable global.
Debe evitarse el uso de variables globales, por tres razones:

-       Ocupan memoria durante toda la ejecución del programa y no sólo cuando se necesitan.
-       El uso de una variable global en lugar de una local, restringirá la generalidad de un subprograma ya que depende de una variable que debe definirse fuera de sí misma.
-       El uso de una serie grande de variables globales puede conducir a errores con efectos laterales desconocido e indeseables.

2.3.  Parámetros Actuales o Reales

Los parámetros actuales son las variables de enlace definidas en el programa principal y que se usan como argumentos dentro de los paréntesis que posee una llamada a un subprograma.

Ejemplo:
main()   {
            char v[20], w[20];
            cout<<”Nombre:”; cin>>v
            cout<<”Apellido:”; cin>>w;
            centro(v, w);    //v y w son parámetros actuales
            }

2.4.  Parámetros Formales o Ficticios

Los parámetros formales son las variables de enlace definidas en la entrada de un subprograma, que aceptan los valores de los parámetros actuales que se usan en la llamada al subprograma y se comportan como otras variables locales.

Ejemplo:
void centro(char *p, char *q)  {         // p y q son P. Formales
            int r, t, x, y;
            r = strlen(p);  x = (79 - r) / 2;
            t = strlen(q);  y = (79 - t) / 2;
            gotoxy(x, 11); cout<<p:
            gotoxy(y, 13); cout<<q;
            }

El subprograma centro tiene dos parámetros formales tipo cadena de caracteres (p y q), en la llamada se puede ver que también existen dos parámetros actuales tipo cadena de caracteres (v y w).
Finalmente se observa que v corresponde a p y w corresponde a q.
En conclusión, los parámetros formales, deben ser semejantes en número, orden y tipo con los parámetros actuales.

3.        Métodos para Diseñar Programas

Existen dos métodos para diseñar subprogramas: procedimientos y funciones. La diferencia esencial entre un procedimiento y una función es que la función obtiene un valor que puede ser utilizado en una expresión, mientras que un procedimiento no tiene ningún valor asociado a su nombre.
Una función puede emplearse en lugar de una variable y el usuario la puede utilizar para crear operaciones nuevas que no están incluidas en las librerías estándar del C++.
Un procedimiento normalmente se utiliza para estructurar un programa y para mejorar la claridad y generalidad.

3.1.  Procedimientos

Un procedimiento es un subprograma que realiza una tarea específica. Esta compuesto por un grupo de sentencias a las que se les asigna un nombre (identificador), y que van a ser ejecutadas como un programa cada vez que se invoca dicho nombre.

3.1.1.      Llamada a un Procedimiento

Sintaxis       :   nombre_procedimiento (parámet_actuales);
Propósito    :   Llamar desde el programa principal o desde otro procedimiento a un procedimiento requerido por su nombre.
Ejemplo      :   leer(m, precios);

En las llamadas a procedimientos se aplica el método denominado: llamada por referencia, que consiste en copiar la dirección de cada parámetro actual en un parámetro formal.

3.1.2.      Declaración de un Procedimiento

Sintaxis      : void nombre_procedim (parám_formals)  {
                        Variables locales
                        Líneas de código de cuerpo de procedimiento
                        }
Propósito    : Declarar un procedimiento indicando nombre y especificando que es un subprograma sin valores de retorno (void). Así mismo, declarar la lista de parámetros formales involucrados en el procedimiento. Es decir, especificar los nombres de tipos y nombres de variables, separados por comas. Estos parámetros son los que reciben valores de los parámetros actuales en la llamada.
Ejemplo     : void reportar (int n, float lista[20])  {
                        int i;              // Definición de variables locales
                        for(i=1;i<=n;i++) cout<<lista[i];
                        // Cuerpo del procedimiento
                        }

Los procedimientos terminan y vuelven automáticamente a la siguiente línea de la sentencia que los llamó en el programa principal, cuando se encuentre con la última llave.
Si un procedimiento carece de parámetros formales, entonces la lista de parámetros estará vacía; pero incluso en este caso se precisan de los paréntesis.
A diferencia de las declaraciones de variables en el programa principal, en las que se pueden declarar, con un solo nombre de tipo, muchas variables separadas por comas.
En la lista de declaraciones de parámetros formales, cada parámetro debe incluir tanto el tipo variable como el nombre, adquiriendo la siguiente sintaxis:

void nomb_proced (tipo1 var1, tipo2 var2,…,tipoN varN)

El siguiente ejemplo tiene una definición incorrecta:

void humos(int s, i, n, float k, r)

La definición correcta es la siguiente:

void humos(int s, int i, int n, float k, float r)

3.1.3.      Retorno de un Procedimiento

El retorno desde un procedimiento al programa principal se produce después que la computadora ejecuta la última sentencia del procedimiento y encuentra al finalizador del procedimiento (}).
En el ejemplo anterior, después de que el procedimiento reporta los valores del vector lista[i], no le queda más que hacer, de manera que vuelve al programa principal, a la siguiente línea de la que la llamó.
Dado que el procedimiento no devuelve ningún valor, se declara como si fuese void.

Gráfica 2. Llamando y retornando de un procedimiento


3.2.  Funciones

Una función es un subprograma que recibe los valores de uno o varios argumentos y devuelve un único resultado al programa o subprograma que lo llamó.
Está formado por una o más sentencias que realizan una tarea determinada.
Cuando se ejecuta la función el resultado es asignado al nombre de la función.
Siempre se utiliza una llamada a una función en una expresión.

3.2.1.      Llamada a una Función

Sintaxis     : variable = nomb_función (parámt_actuales);
Propósito   : Llamar desde el programa principal o desde algún procedimiento a una función requerida por su nombre.
Ejemplo     : y = acumulativa (m, x);

En el caso de llamadas a funciones se aplica el método denominado: llamada por valor, que consiste en copiar el valor de cada parámetro actual en un parámetro formal de la función.
Por lo tanto, los cambios que se hacen a los parámetros formales no tienen efecto en los parámetros actuales. Ejemplo:

main()    {
                        int k = 15;
                        cout<<sum(k)<<k;
                        }
            int sum(int z)     {
                        z = z + z;
                        return(z);         }

Esta función copia el valor del parámetro actual k a sum(), en el parámetro formal z.
Cuando tiene lugar la asignación z = z + z, lo único que se modifica es la variable local z. La variable k, usada para llamar a sum(), todavía tendrá el valor 15.
La salida de la función será 30.

3.2.2.      Declaración de una Función

Sintaxis     : tipo nomb_función (parámetros_formales)  {
                        Variables locales
                        Líneas de código del cuerpo de la función    }
Propósito   : Declarar una función indicando su nombre y especificando el tipo de valor que la función devolverá. Así mismo, declarar la lista de parámetros formales involucrados en la función. Es decir, especificar los nombres de tipos y nombres de variables separados por comas. Estos parámetros son los que recibirán los valores de los parámetros actuales cuando se llame a la función.
Ejemplo    : float acumulativa (int n, float k[30]) 
                        int i, flota s=0;    // Variables locales
                        for(i=1; i<=n; i++) s=s+k[i];  // Cuerpo función
                        return(s);    }

El valor de la función puede ser de cualquier tipo válido; si no se especifica, se asume que por defecto la función devolverá un valor entero.
Si una función carece de parámetros, entonces la lista de parámetros estará vacía; pero incluso en este caso se precisan de los paréntesis.
En las funciones, la declaración de parámetros formales es semejante a la que se hace en los procedimientos:

tipo nomb_función (tipo1 var1, tipo2 var2,..., tipoN varN)

3.2.3.      Retorno desde una Función

Sintaxis     : return expresión;
Propósito   : Devolver un valor desde una función y provocar que el programa en su ejecución salga de la función en la que está y retome de inmediato al código que llamó a dicha función.
Ejemplo     : return(s);

Las funciones que devuelven valores son de tres tipos:

-       Funciones que realizan específicamente operaciones sobre sus parámetros actuales y devuelven un valor basado en ese cálculo. Ejemplo: las funciones de biblioteca como tan() que devuelve la tangente de un ángulo en radianes.
-       Funciones que manipulan información y devuelven un valor que indica si esta manipulación salió bien o falló. Ejemplo: la función fwrite() que se usa para escribir datos sobre un archivo de disco. Si tiene éxito la escritura, entonces fwrite() devolverá el número de bytes que se pidió que escribiera, cualquier otro valor indicará que ha ocurrido un error.
-       Funciones que no tienen un valor de retorno explícito. En esencia, la función es estrictamente procesal y no produce un valor. Si no se especifica una asignación, entonces la computadora simplemente descarta el valor devuelto.
Ejemplo:

main()  {
int h, j, k;
h = 9;   j = 5;
k = resto(h, j);             // Línea 1
cout<<resto(h, j);         // Línea 2
resto(h, j);                   // Línea 3
}

int resto(int p, int q)     {
return p % q;
}

La línea 1 asigna el valor devuelto por resto() a k. En la línea 2, el valor devuelto no está realmente asignado, sino que cout lo usa. Y en la línea 3, el valor devuelto se pierde porque no lo asigna a otra variable, ni la usa como parte de una expresión.
Una función no puede ser objeto de una asignación. Por ejemplo la siguiente sentencia es incorrecta:

Suma(x, y) = 350;

4.        Llamada a Subprogramas con Arreglos

Cuando se usa a un arreglo como un parámetro actual, se pasa sólo la dirección del arreglo al subprograma y no se copia el arreglo completo.
Es decir, que cuando se llama a un subprograma con un nombre de arreglo, la declaración de parámetros debe ser de un tipo puntero, dirigido al primer elemento del arreglo del subprograma.
Hay tres formas de declarar este tipo de parámetro:

-       Declarándolo como un arreglo.
-       Especificando el parámetro como un arreglo sin tamaño
-       Declarándolo como un puntero

a)        Declarándolo como un arreglo.

Ejemplo:
main()     {
int q[20], j;
for(j=0; j<20; j++) q[j] = j;
reporte(q);     }

reporte(int x[20])        {
int j;
for(j=0; j<20; j++) cout<<x[j]);    }

Aunque este programa declare al parámetro x como un arreglo de veinte elementos enteros, el C++ convertirá automáticamente x a un puntero entero.

b)        Especificando parámetro como un arreglo sin tamaño.

Ejemplo:
reporte(int x[])    {
int j;
for(j=0; j<20; j++) cout<<x[j]);
}

Este código declara a x como un arreglo de enteros de tamaño desconocido.
Este método de declaración también define a x como un puntero entero.

c)        Declarándolo como un puntero.

Ejemplo:
reporte(int *x)   {
int j;
for(j=0; j<20; j++) cout<<x[j]);
}

Los tres métodos de declaración de un parámetro de arreglo dan el mismo resultado: un puntero.
Pero la forma más común en los programas escritos profesionalmente, es el tercero.

5.        Prototipos de Subprogramas

Sintaxis     : tipo nombre_subprog(tipo1 par1, tipo2 par2,..., tipoN parN);
Propósito   : Definir el nombre de un subprograma antes de usarlo y el tipo de dato que este devuelve. Declarar número, tipos y orden de parámetros formales que el subprograma espera recibir. Definición de prototipos es obligatoria cuando subprograma se declara después del programa principal o del subprograma que lo llamó. En caso contrario, esta definición es obviada. El compilador usa prototipos de subprogramas para validar las llamadas de subprogramas.
Ejemplo     : int equipo(int, int, float);

Los tipos de datos que están entre paréntesis le informa al compilador que el subprograma equipo espera que el invocador le devuelva dos valores enteros y uno flotante.
El tipo de dato (int) a la izquierda del nombre del subprograma le informe al compilador que equipo le devuelve un resultado entero al invocador.
En el caso de que uno de los parámetros formales del subprograma sea arreglo, este se puede definir de 2 formas:
En forma subíndicada, por ejemplo:

int estrategia(int x[20], int);

En forma de puntero, por ejemplo:

int estrategia(int *, int);

6.        Tipos de Subprogramas

Existen dos tipos de subprogramas:

-       Subprogramas internos, son los subprogramas que figuran junto con el programa principal (en el mismo listado).
-       Subprogramas externos, son los subprogramas que figuran físicamente separados del programa principal, es decir, en distintos archivos fuente.

Pueden ser compilados separadamente y generalmente se enlazan con el programa principal en la fase de montaje, cuando ya son módulos objeto, es decir, traducidos a lenguaje de máquina.
Los archivos de estos subprogramas pueden ser incluidos en el encabezamiento del programa principal usando la siguiente sintaxis:

#include <unidad: \ ruta \ nombre_archivo . extensión>

Por ejemplo:
#include <c: \ borlandc \ bin \ estadistica . h>

Esta directiva incluye a todos los subprogramas que han sido salvados previamente en el archivo denominado estadistica.h que se encuentra en la ruta borlandc\bin de la unidad C:

7.        Atributos de Identificadores de Subprogramas

En los capítulos anteriores hemos utilizado identificadores para los nombres de las variables, los atributos de estos identificadores incluyen: nombre, tipo, tamaño y valor.
En este capítulo también utilizamos identificadores como nombres de subprogramas definidos por el usuario. De hecho, los identificadores de los subprogramas tienen otros atributos, tales como: clase de almacenamiento, alcance y enlace.

7.1.  Clase de Almacenamiento

La clase de almacenamiento del identificador determina el periodo durante el cual existe en memoria dicho identificador.
Algunos identificadores existen durante un periodo breve, otros se crean y destruyen repetidamente y otros existen durante toda la ejecución del programa.
Los especificadores de clase de almacenamiento pueden dividirse en:

-       Clase de almacenamiento automático.
-       Clase de almacenamiento estático

7.1.1.   Clase de Almacenamiento Automático

Sintaxis     : auto tipo nombre_variable;
Propósito   : Declarar variables de clase de almacenamiento automático.
Ejemplo     : auto float r, t;

Las variables locales y los parámetros de una función normalmente son de esta clase.
De manera predeterminada, las variables locales son de la clase de almacenamiento automático por lo que pocas veces se utiliza la palabra clave auto.
Esta clase es un medio eficiente para conservar memoria sólo cuando se necesita, ya que existen mientras el bloque está activo y se destruyen al salir de él.

Sintaxis     : register tipo nombre_variable;
Propósito   : Sugiere al compilador que mantenga a una variable automática en uno de los registros de hardware, que son de alta velocidad, en lugar de en memoria.
Ejemplo     : register int k=1;

Las variables de uso intensivo (contadores), pueden mantenerse en registros de hardware, con lo cual es posible eliminar la sobrecarga
La palabra clave register sólo puede utilizarse con variables y parámetros de funciones locales.
Frecuentemente estas declaraciones son innecesarias.

7.1.2.   Clase de Almacenamiento Estático

Sintaxis     : extern tipo nombre_variable;
Propósito   : Declarar variables y nombres de funciones globales. Las variables globales se crean poniendo declaraciones de variables fuera de todas las definiciones de funciones.
Ejemplo     : extern float x;

Las variables y funciones de esta clase existen desde el momento en que se inicia la ejecución del programa.
Sin embargo, aunque las variables y los nombres de función existan desde el inicio de la ejecución, esto no significa que puedan utilizarse en todo el programa.
Generalmente se usan para declarar variables globales.

Sintaxis     : static tipo nombre_variable;
Propósito   : Declarar variables locales que son conocidas solo en la función en la que se define; pero, a diferencia de las variables automáticas, estas variables locales conservan sus valores al salir de la función. La siguiente vez que se llama a la función, las variables locales static contendrán valores que tenían al salir de ella la última vez.
Ejemplo    : static int w=3;

Todas las variables numéricas de la clase de almacenamiento estático se inicializan a cero si el programador no las inicializa a un valor explícito.

7.2.  Alcance

El alcance de un identificador es la parte del programa en la que un identificador tiene significado.
Ejemplo, cuando se declara una variable local en un bloque, se puede referenciar sólo en dicho bloque o en bloques anidados dentro de él.

-       Alcance de archivo. En este tipo de alcance los identificadores son “conocidos” por todas las funciones desde el momento en que se declara el identificador hasta el final del archivo. Para ello, los identificadores deberán ser declarados fuera de cualquier función. Las variables globales, las definiciones de funciones y los prototipos de función colocados fuera de una función tienen este alcance.
-       Alcance de función. En este tipo de alcance los identificadores pueden usarse en cualquier parte de la función en la que aparezcan, pero no pueden referenciarse desde fuera del cuerpo de la función. Los únicos identificadores de este tipo son las etiquetas. Las etiquetas sirven en las estructuras switch y en las instrucciones goto.
-       Alcance de bloque. Este tipo de alcance comienza con la declaración del identificador dentro de un bloque y termina con la llave de terminación del bloque ( } ). Tienen este tipo de alcance las variables locales declaradas al inicio de una función y los parámetros formales de función. Si un bloque es anidado y un identificador de un bloque externo tiene el mismo nombre que un identificador de un bloque interno, se “oculta” el identificador del bloque externo hasta que termina el bloque interno. 
Alcance de prototipo de función. Este tipo de alcance tiene como únicos identificadores a aquellos que se usan en la lista de parámetros de un prototipo de función. Los prototipos de función no requieren nombres en la lista de parámetros, sólo se necesitan los tipos. Si se indica un nombre en la lista de parámetros de un prototipo de función, el compilador lo ignora. Los identificadores usados en los prototipos

Ejemplo:
Ingresar el número de elementos de dos vectores (M y N), así como cada uno de los elementos de los vectores que definen a la variable independiente X(i) y a la variable dependiente Y(j); usar en este caso el procedimiento Ingreso(). Si el número de elementos de ambos vectores son iguales, calcular la intersección de la recta con la ordenada (A) y la pendiente (B) usando el método de los mínimos cuadrados (análisis de regresión). Luego ingresar el valor de un dato correspondiente a la variable independiente y determinar el pronóstico respectivo. En caso contrario, calcular la suma de los elementos de cada vector. Usar procedimientos y funciones.

Análisis:
La pendiente de la recta (B) se calcula utilizando la siguiente expresión estadística:

 



La intersección con la ordenada (A) se calcula usando la siguiente expresión estadística:

 



La ecuación del pronóstico es la siguiente:

Y = A + B X

Codificación:
#include <iostream.h>      // Regresión lineal
#include <conio.h>
#define LIM 10
int x[LIM];                        // Elementos del vector de la variable independiente
int y[LIM];                        // Elementos del vector de la variable dependiente
void main()     {
void ingreso(int, int *, char *);
int suma(int, int *);
long int sumaxy(int, int *, int *);
long int sumax2(int, int *)
int m;                                 // Tamaño del vector de la variable independiente
int n;                                   // Tamaño del vector de la variable dependiente
int p;                                   // Suma de elementos de la variable independiente
int q;                                   // Suma de elementos de la variable dependiente
long int r;                            // Suma de productos de los elementos de ambos vectores
long int t;                            // Suma de cuadrados de la variable independiente
float a;                                 // Intersección con la ordenada
float b;                                 // Pendiente de la recta
float v;                                 // Valor de variable independiente a pronosticar
float w;                                // Valor de pronóstico de variable dependiente
clrscr();
gotoxy(10,2); cout<<"Número de elementos del primer vector : ";
gotoxy(51,2); cin>>m;
gotoxy(10,4); cout<<"Número de elementos del segundo vector: ";
gotoxy(51,4); cin>>n;
ingreso(m, x, "Elementos del primer vector: ");
ingreso(n, y, "Elementos del segundo vector: ");
if(m==n)     {
p=suma(m, x);  q=suma(m, y);  r=sumaxy(m, x, y);  t=sumax2(m, x);
b=(float) (m*r-p*q)/(m*t-p*p);  a=(q/m)-b*(p/m);
clrscr();
gotoxy(10,2);  cout<<"Línea recta";
gotoxy(10,5); cout<<"Intersección con la ordenada    : "<<a;
gotoxy(10,7); cout<<"Pendiente                       : "<<b;
gotoxy(10,10); cout<<"Valor de variable independiente : ";  cin>>v;
w=a+b*v;
gotoxy(10,12); cout<<"Pronóstico                      : "<<w;    }
else  {
p=suma(m, x);   q=suma(n, y);
clrscr();
gotoxy(10,2);  cout<<"Suma de elementos";
gotoxy(10,5); cout<<"Primer vector  : "<<p;
gotoxy(10,7); cout<<"Segundo vector : "<<q;    }
getch();
}
void ingreso(int n, int x[LIM], char mensaje[15])    {
register int i;                            // Subíndice de la variable independiente o dependiente
clrscr();  gotoxy(10,2);  cout<<mensaje;
for(i=1;i<=n;i++)     {
gotoxy(10,3+i); cout<<"Ingrese elemento "<<i<<": ";
gotoxy(38,3+i); cin>>*(x+i);    }
}
int suma(int k, int x[LIM])     {
register int i;                            // Subíndice de la variable independiente o dependiente
int s=0;                                    // Suma de los elementos del vector
for(i=1;i<=k;i++) s=s+*(x+i);
return(s);
}
long int sumaxy(int k, int x[LIM], int y[LIM])    {
register int i;                            // Subíndice de las variables independiente y dependiente
int s=0;                                    // Suma de los productos de los elementos de ambos vectores
for(i=1;i<=k;i++) s=s+*(x+i)**(y+i);
return(s);
}
long int sumax2(int k, int x[LIM])    {
register int i;                            // Subíndice de las variables independiente y dependiente
int s=0;                                    // Suma de los cuadrados de los elementos del vector independiente
for(i=1;i<=k;i++) s=s+*(x+i)**(x+i);
return(s);
}