Exibir código-fonte para Revisão de C: Ponteiros e funções (recursivas e iterativas)

Links Relacionados: [[DAS5102 Fundamentos da Estrutura da Informação]]

= Ponteiros e Funções =

Funções ou sub-rotinas são parcelas de código que podem ser invocadas a partir do programa principal ou até mesmo por outras sub-rotinas. Elas têm como objetivo a execução de uma tarefa específica. Funções são também criadas por motivos de modularização, uma vez que a mesma função pode ser utilizada por diversos programas. Finalmente, a utilização de funções é uma forma eficiente de organizar o código fonte, separando do programa principal partes funcionais do código com objetivos claros e bem definidos.

Funções em C apresentam a seguinte forma geral:

<syntaxhighlight lang=c line>
<tipo> <nome_funcao>(<tipo> <parametro>) 
{ 
   //código da função 
}
</syntaxhighlight>
'''<small>Figura 1 – forma geral de uma função em C </small>'''

Adicionalmente, funções podem possuir mais de um parâmetro. Para tal, basta declaramos os parâmetros adicionais acompanhados de seus tipos dentro dos parênteses, Parâmetros adicionais devem ser separados por vírgula.

Argumentos podem ser passados para uma função de duas formas distintas:

* Passagem de parâmetros por valor; 
* Passagem de parâmetros por referência.

{| class="wikitable" style="margin: 1em auto 1em auto"
|+ '''Comparação entre passagem de parâmetros por valor e por referência'''
! Parâmetros Por Valor !! Parâmetros Por Referência
|-
| Uma cópia da variável é feita e armazenada na pilha 
| Nenhuma cópia da variável e feita
|-
| Ideal para casos em que o tamanho da variável é pequeno
| Ideal para casos em que o valor original da variável deve ser alterado por uma função
|-
| Quando a variável é grande (arrays) o consumo de memória na pilha pode ser proibitivo 
| Requer cuidado adicional em se manipular os argumentos da função
|-
| Torna a chamada de funções lenta dependendo do tamanho dos argumentos
| Chamada de função é sempre rápida
|}
'''<small>Figura 2 – comparação entre passagem de parâmetros por valor e por referência.</small>'''

A utilização de ponteiros é a maneira pela qual a linguagem C passa parâmetros para uma função por referência. Existem diversas situações nas quais a passagem de parâmetros por referência pode ser desejada (veja figura 2). 

Em C, parâmetros são passados por referência utilizando ponteiros. Ao atribuir uma variável ponteiro como parâmetro de uma função o que é feito realmente é atribuir o endereço da variável. Desta forma, nenhuma cópia da variável é feita na pilha do programa, mas sim, a variável original é utilizada.


<syntaxhighlight line>
<tipo> <nome_funcao>(<tipo> *<parametro>) 
{ 
  //código da função 
}
</syntaxhighlight>
'''<small>Figura 3 – forma geral de uma função em C, parâmetros são passados por referência.</small>'''

Existem várias situações onde a passagem de parâmetros por referência para funções são desejáveis: 

* Quando a quantidade de dados a ser passada como referência é muito grande;
* Quando desejamos que a função altere o valor de uma variável ou estrutura de dados existente no escopo do programa que invoca a função;
* Quando a função a ser chamada deve executar rapidamente.

Observe o programa exemplo apresentado na figura 4. Neste pequeno programa pode-se observar o funcionamento da passagem de parâmetros  por referência. Observe que o endereço da variável '''valor''' deve ser passado, e observe que ao utilizarmos a variável '''val''' na função '''incrementaValor''' devemos referenciá-la usando a notação de ponteiros e não diretamente.

<syntaxhighlight lang=c line>
#include <stdio.h>

void incrementaValor(int *val);

void main( void )
{
    int valor = 100;
    incrementaValor(&valor);
    printf("%d",valor);
}

void incrementaValor(int *val)
{
    //val = val + 1; //porque isso não funciona?
    //*val = *val + 1;
    (*val)++;
}
</syntaxhighlight>
'''<small>Figura 4 – código exemplo para passagem de parâmetros por referência</small>''' 

= Alocação Dinâmica de Memória =

Alocação dinâmica de memória é o meio pelo qual um  programa pode obter memória enquanto está em execução. 

* Variáveis globais e locais têm espaço alocado em tempo de compilação; 
* Parâmetros de funções têm espaço alocado na pilha.

<syntaxhighlight lang=c line>
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
int main()
{
    char texto[10];
    short idades[10];
    int indices[10];
    float porcentagens[10];
    double fatores[10];
    printf ("\n\nDado char: %d byte", sizeof(char));
    printf ("\nEspaco para 'char texto [10]': %d bytes",sizeof(texto));
    printf ("\n\nDado short: %d bytes",sizeof(short));
    printf ("\nEspaco para 'short idades [10]': %d bytes",sizeof(idades));
    printf ("\n\nDado int: %d bytes",sizeof(int));
    printf ("\nEspaco para 'int indices [10]': %d bytes",sizeof(indices));
    printf ("\nEspaco para 'int indices [10]': %d bytes",sizeof(indices));
    printf ("\n\nDado float: %d bytes",sizeof(float));
    printf ("\nEspaco para 'float porcentagens [10]': %d b ytes",sizeof(porcentagens));
    printf ("\n\nDado double: %d bytes", sizeof(double));
    printf ("\nEspaco para 'double fatores [10]': %d bytes",sizeof(fatores));
    //getch();
    return 0;
}
</syntaxhighlight>
'''<small>Figura 5 – código para a determinação do tamanho em bytes dos tipos nativos.</small>'''

Alocação dinâmica obtém memória da heap, que é essencialmente a parte livre da memória alocada para o processo. 

Alocação dinâmica em C é controlada basicamente por duas funções:

* '''malloc( )''' – obtém memória da heap. Retorna um ponteiro do tipo void para a primeira posição de memória alocada, ou NULL em caso de falha.
* '''free( )''' – libera memória previamente alocada para uso posterior. Recebe como parâmetro um ponteiro para a parte da memória a ser liberada.

As funções malloc e free são definidas na biblioteca <stdlib.h>. Seus protótipos são: 

<syntaxhighlight lang=c line>
void *malloc(size_t numero_de_bytes); 
void free( void *p ); 
</syntaxhighlight>

É muito importante testar se uma chamada de malloc foi ou não bem sucedida. Similarmente, deve-se sempre tomar cuidado em passar para a função free um ponteiro para uma região de memória que foi alocada. A utilização de um ponteiro inválido pode vir a acarretar sérios problemas (geralmente ocorrerá um erro de “segmentation fault”, o que fará com que o programa seja interrompido). 

<syntaxhighlight lang=c line>
char *p; 
p = malloc( 1000 ); // obtem 1000 bytes
</syntaxhighlight>

<syntaxhighlight lang=c line>
#include <stdio.h> 
#include <stdlib.h> 
main () 
{ 
    int *p, a, i; 
    // ... 
    p=(int *)malloc(a*sizeof(int)); 
    if (!p)
    { 
        printf ("** Erro: Memória Insuficiente **"); 
        exit (1); 
    } 
    for (i=0; i<a ; i++)
    {
        p[i] = i*i;
    }
}
</syntaxhighlight>

= Recursão =
Recursão é um conceito fundamental em matemática e  ciências da computação. Em programação uma função é dita recursiva se ele chama a si mesma, e em matemática, funções recursivas são funções definidas em termos delas mesmas. 

O exemplo mais clássico de funções recursivas é a função fatorial. 

 N! = N*(N-1)!

<syntaxhighlight lang=c line>
int fatorial (int N)
{ 
    if (N==0) return 1; 
    return N * fatorial(N-1); 
} 
</syntaxhighlight>

Um dos quesitos mais importantes no que se refere a funções recursivas é a chamada '''condição de parada'''. A condição de parada é a forma pela qual a função recursiva para de se chamar a si mesma. Sem uma condição de parada, funções recursivas podem entrar em um 
loop infinito, uma situação muito similar ao exemplo a seguir: 

<syntaxhighlight lang=c line>
while(1)
{ 
    //código do laço 
}
</syntaxhighlight>

Funções recursivas provêm o programador de uma maneira intuitiva para modelar muitos problemas. No entanto, funções recursivas fazem uso extensivo da pilha de chamada de funções. Se não bem dimensionadas, elas podem induzir um erro chamado ''Stack Overflow'' que acontece quando o espaço reservado para a pilha de chamadas de função é superado.

= Exercícios =

1. Crie um programa que leia ''n'' idades (inteiras),armazene -as e depois mostre-as. O valor de ''n'' será informado pelo usuário. Crie funções e procedimentos para realizar as tarefas.

<syntaxhighlight lang=c line>
#include <stdio.h> 
#include <stdlib.h> 

int criarvetor (int n); 
void lervetor (int n); 
void mostrarvetor (int n); 

int *idades; // ponteiro utilizado na alocação

int criarvetor (int n)
{ 
    idades = (int*) malloc ((n)* sizeof(int)); // alocação 
    if (idades == NULL)
    { 
        printf ("\nErro reservando memoria"); 
        return 0; 
    } 
    return 1; 
}

void lervetor (int n)
{ 
    int i, *cont = idades; 
    for (i = 0;i < n; i++)
    { 
        printf ("\nDigite o elemento %d ", i + 1); 
        scanf ("%d",cont++); 
    } 
}

void mostrarvetor (int n) 
{ 
    int i, *cont = idades; 
    for (i = 0; i < n; i++)
    { 
        printf ("\nO elemento %d eh %d ",i + 1, *cont++); 
    } 
}

int main()
{  
    int n; 
    printf ("\n Quantas idades deseja cadastrar ? ");
    scanf ("%d",&n); 
    if (criarvetor(n))
    { 
        lervetor(n); 
        mostrarvetor(n);
        free (idades); // Liberar memória alocada 
    }
    return 0;
}
</syntaxhighlight>

2. Explique a diferença entre alocação estática e alocação dinâmica de memória.

3. Explique a função que o ponteiro tem na alocação dinâmica.

4. Faça um programa para alocar espaço para colocar o nome do usuário (30 caracteres). Se conseguir alocar, leia esta string e mostre-a ao contrário.

5. As funções recursivas tem uma demanda maior de memória. Por que?

6. O que significa ''size_t'' ?

7. Em qual biblioteca (.h) fica o sizeof ?

8. Qual a utilidade do sizeof no tocante a portabilidade ? 

9. Construa um programa que leia da entrada padrão o número de linhas e de colunas de uma matriz de ''floats'', aloque espaço dinamicamente para esta e a inicialize, com valores fornecidos pelo usuário, através da entrada padrão. Ao final o programa deve retornar a 
matriz na saída padrão com layout apropriado.

10. Crie uma biblioteca de funções que gerencie a alocação dinâmica de vetores. Para alocação do vetor a biblioteca deve, ter a seguintes função:

<syntaxhighlight lang=c line>
int aloca(int*  &ptr, int tam)
{   
    // aloca um vetor de 'tam' inteiros, retornando 1 se foi possível alocar e 0 se não foi
    // o parâmentro 'ptr' deve retornar com o apontador para a área alocada 
}
</syntaxhighlight>

11. Usando sobrecarga de funções, crie uma rotina com o mesmo nome da anterior, que aloque vetores de ''floats''. 

12. Crie funções para preencher os elementos de vetor com um certo valor. Para varrer o vetor, não utilize índices, use apenas aritmética de ponteiros. Faça isto para os vetores de inteiros e de reais.

<syntaxhighlight lang=c line>
void preenche(int* vet, int tam, int n)
{ 
    // atribui a todos os elementos do vetor 'vet' o valor 'n' 
    // não use índices. Use apenas aritmética de ponteiros. 
}
</syntaxhighlight>

13. Crie funções para imprimir os elementos de vetor. Para varrer o vetor, não utilize índices, use apenas aritmética de ponteiros. Faça isto para os vetores de inteiros e de reais.

= Roteiro =

== Objetivos ==

* Revisar a passagem de parâmetros por referência para funções; 
* Revisar os métodos de iteração e recursão.

== Exercício 1 ==

Crie um arquivo chamado ''malloc_free.c'' utilizando um editor de textos padrão (vi, pico, xemacs, gedit) e digite o seguinte programa:

<syntaxhighlight lang=c line>
#include <stdio.h>
#include <stdlib.h>

int main( void )
{
    int numInteiros = 0;
    int *pInt, *pIntInit;
    int tempInt;
    int count;
    printf( "Digite o numero de inteiros a ser lido:" );
    scanf( "%d", &numInteiros );
    if ( !(pInt = malloc( numInteiros * sizeof(int))))
    {
        printf("sem memória!\n");
        exit( 1 );
    }
    pIntInit = pInt;
    for(count = 0; count < numInteiros; count++)
    {
        printf( "\n Digite o inteiro [%d]:",count );
        scanf( "%d", &tempInt );
        *pInt = tempInt;
        pInt++;
    }
    int acc = 0;
    pInt = pIntInit;
    for(count = 0; count < numInteiros; count++)
    {
        acc = acc + *pInt;
        pInt++;
    }
    printf("%d", acc);
    free( pIntInit ); // libera a memória alocada dinâmicamente
    pIntInit = pInt = NULL;
    exit( 0 );
}
</syntaxhighlight>

=== Como compilar o programa ===

 gcc malloc_free.c –o malloc_free 

=== Atividades ===

a) Escreva uma função que receba o vetor de inteiros “pInt” passado como parâmetro e inverta a ordem dos números; (DICA, gere uma cópia temporária do vetor de inteiros );

b) Escreva uma função que receba o vetor de inteiros “pInt” passado como parâmetro por referência e substitua todos os números do vetor pelas seus quadrados.

== Exercício 2 ==

Crie um programa que leia do usuário um número. Este número deve ser maior que 0 e menor que 20. Em seguida o programa deve calcular a série de Fibonacci deste número. Todos os elementos da série de Fibonacci devem ser  salvos em um vetor alocado dinamicamente.

[[Image:Fibonacci.png]]