1Estruturas de Dados

Reviso de Funes e Recurso

Prof. Ricardo J. G. B. Campello

AgradecimentosParte dos slides a seguir so adaptaes dos

originais em Pascal gentilmente cedidos pelo Prof. Rudinei Goularte

2Sumrio

Funes em C Declarao, Escopo e Tipos de Passagem

Funes Pr-Definidas em Bibliotecas

Ativao de Funes

Recurso Definio e Caractersticas

Tipos de Recurso

Funes em C

Podemos ver uma funo em C como uma rotina que recebe ou no valores como argumentos e retorna ou no explicitamente um valor

Declarao:

tipo nome (lista de parmetros) {corpo da funo (incluindo declaraes de vars. locais)

}

Exemplo:

double quadrado (double x) {return x*x; }

3Funes em C

Funes que no retornam valores so do tipo void

void tambm usado para indicar a inexistncia de parmetros

Exemplo:void hello(void){

printf("Hello World!");}

O retorno de valor feito atravs do comando return

return interrompe imediatamente o fluxo de execuo

e retorna o valor especificado

Funes em C

Escopo:

As variveis declaradas dentro de uma funo possuem escopo local, ou seja, provisrio e interno funo

Variveis globais so declaradas no incio de qualquer mdulo (arquivo) de programa, fora de qualquer funo

incluindo main !

Passagem de Parmetros:

Em geral, por valor (uma cpia do parmetro feita)

Para forar passagem por referncia, preciso utilizar ponteiros

o que ocorre necessariamente com arranjos (vetores/matrizes)

4 As linguagens de programao tm sua disposio vrias funes pr-definidas

Em C, essas funes so organizadas em bibliotecas

Exemplo (Biblio. Matemtica C ANSI #include ):

pow(b,e) base b elevada ao expoente e

sqrt(x) raiz quadrada de x

Funes Pr-Definidas

Parmetro formalIdentificador (nome)

Ativao de Funes

Ativao e captura do resultado de uma funo pode ser:

Por atribuio direta do retorno a uma varivel do mesmo tipo

Por uso do retorno dentro de uma expresso

Exemplo (H real, A e Y so inteiros ou reais):

H = sqrt(A + pow(Y,2) + 2 * sin(Y));

atribuio direta uso em expresso

5Exemplo

Dados dois nmeros N e K, calcular a Combinao:

Se existisse uma funo fat(X) que calculasse o fatorial de um dado X, o clculo acima ficaria:

C[N,K] = fat(N) / (fat(K) * fat(N-K))

Se no existe, podemos defini-la

( ) )!(!!

,

KNKNKNC

=

long int FAT(long int X){long int I, P;P = 1;for(I=1; I

6Exemplo

#include

long int FAT(long int X);

void main(void){long int N, K, C;printf("Entre com N:");scanf("%d", &N);printf("Entre com K:");scanf("%d", &K);C = FAT(N)/(FAT(K)*FAT(N-K));printf("\n C(N,K) = %d", C);

} /* continua ... */

/* continua ... */

long int FAT(long int X){long int I, P;P = 1;for(I=1; I

7Recurso

long int FAT(long int x) {if (x == 1) return 1;else return x*FAT(x1); }

Em C, qualquer funo pode ser usada recursivamente Exemplo: clculo do fatorial

long int FAT(long int x) {return (x == 1 ? 1 : x*FAT(x1) );

} /* EPC: Modifique para funcionar para x = 0 */

OU

Recurso

Exige condio de parada e mudana de estado ou entra em ciclo infinito at estourar a pilha de recurso

Quais so elas no cdigo recursivo do fatorial ???

Vantagens Muitos problemas so intrinsecamente recursivos

Cdigo possivelmente mais claro (simples)

Desvantagens Velocidade (chamadas a mdulos demandam tempo)

Uso adicional de memria (pilha de recurso)

Anlise terica possivelmente mais complexa

8Recursofloat vetsum(float v[], int n){

if (n == 0) return v[0];else return ( v[n] + vetsum(v, n1) );

}

Trao de recurso:

vetsum(v,4)

vetsum(v,0)

vetsum(v,1)

vetsum(v,2)

vetsum(v,3)

retorna v [0] = 4

retorna 4 + v [1] = 4 + 3 = 7

retorna 7 + v [2] = 7 + 6 = 13

retorna 13 + v [3] = 13 + 2 = 15

retorna 15 + v [4] = 15 + 5 = 20

Exemplo com v = [4 3 6 2 5]

Recurso Alguns Tipos de Recurso:

Recurso Linear: Mdulo com apenas uma chamada recursiva

Recurso Binria: Mdulo com duas chamadas recursivas

Recurso Mltipla: Mdulo com mltiplas chamadas recursivas

Recurso Indireta: Mdulo A chama B que chama A

Recurso de Cauda:

Recurso linear cuja chamada recursiva a ltima operao do mdulo

Note que, tecnicamente, a recurso da funo fat vista anteriormente no de cauda, mesmo estando na ltima declarao do mdulo:

de fato, a ltima operao do mdulo uma multiplicao

no entanto, usual chamar esse tipo de recurso como de cauda

9Recurso Sempre existe verso iterativa de um programa recursivo

Converso nem sempre trivial

Normalmente simples para recurso do tipo cauda

Exemplo 1: impresso de vetorvoid printvet(float v[], int i, int f){

if (i

10

Recurso Situaes onde se recomenda usar recurso:

Quando o problema intrinsecamente recursivo (e.g. Srie de Fibonacci) e sua soluo como tal traz maior clareza e no implica ineficincia em termos de tempo de execuo e uso de memria.

Situaes onde se deve evitar recurso:

Quando existe um algoritmo iterativo igualmente claro e simples

P. ex. quando a recurso de cauda

P. ex. quando uma nica recurso j leva condio de parada

Quando a recurso ineficiente perante a uma verso iterativa

P. ex. quando muitos parmetros so passados por valor

P. ex. quando pode haver sobrecarga da pilha de recurso

Exerccios Qual o efeito final de inverter as linhas 3 e 4 do procedimento recursivo printvet visto anteriormente ?

Escreva uma funo recursiva que receba uma base real e um expoente inteiro e retorne o valor da base elevada ao expoente.

simples provar por induo matemtica que a relao de recorrncia Tn = 2Tn1 + 1 , para T0 = 0, equivalente a Tn = 2n 1. Escreva duas funes que recebam um inteiro n e retornem Tn, sendo uma recursiva e a outra no.

Implemente uma funo para calcular o n-simo elemento da seqncia de Fibinacci de forma recursiva.

11

BibliografiaSchildt, H. "C Completo e Total", 3a. Edio, Pearson, 1997.

Damas, L. Linguagem C, 10a. Edio, LTC, 2007