Programação Básica 04 - Funções

Aula de Rogério Júnior

Nas aulas passadas, já usamos algumas funções, como scan e printf, strlen e strcmp. Perceba como funciona uma função genérica: ela é chamada pelo nome,e realiza uma séria de comandos, bem como retornar uma variável ou não, que dependem dos parâmetros que foram inseridos nela entre parênteses. Enfim, para chamarmos uma função genérica cujo nome seja funcao, escrevemos o comando "funcao(parametro1, parametro2, parametro 3, ...);". No scanf, por exemplo, os parâmetros são primeiro uma string (tudo que está entre aspas duplas), e depois uma série de ponteiros, ou seja, "endereços" para algumas variáveis. Na strcmp, os parâmetros são duas strings. O retorno de uma função é o valor que ela assume em função de seus parâmetros. A scanf retorna um inteiro: o número de objetos armazenados com sucesso, e, se ela para de funcionar antes de ler o que esperava, por fim de arquivo, ela retorna EOF (End Of File), que é -1. A strlen também retorna um inteiro, o tamanho de uma string. Veja portanto, que todas essas funções são do tipo int, pois retornam inteiros.

Assim como podemos declarar variáveis, também podemos declarar funções. Elas devem ser declaradas fora da main, pois não podemos declarar uma função dentro de outra. Vale lembrar, também, que elas devem ser declaradas antes da main, pois o computador executa comandos na ordem que lê e, assim como com as variáveis, não podemos chamar uma função sem antes declará-la.

A gramática da declaração de uma função começa pelo tipo da função (int, double, char, ...), depois abrimos parêntese e declaramos os parâmetros da função, dizendo seus tipos e nomes e os separando por vírgula. Fechados os parênteses, abrimos chaves e escrevemos os comandos que a função deve executar, que podem usar os parâmetros declarados. O que a função irá retornar é um comando que deve estar entre as chaves. Para fazermos a função retornar um valor x qualquer, que deve ser do mesmo tipo da função, escrevemos "return x;". Lembre-se que uma função fecha imediatamente após retornar um valor. Existe um tipo de função que não retorna nada, a void. A usamos somente para executar comandos, e não esperamos que ela assuma algum valor após executá-los. Ainda podemos usar o return nela, mas apenas como ordem para que encerre, sem retornar valor algum, através do comando "return;". Segue, para melhor fixação, um programa que, dados dois números, imprime o maior deles através da função $max$, que recebe dois inteiros e retorna o maior deles:

A lógica da função acima é muito simples: se (a>b) retorne a como valor da função. Se a função não retornar, então a não era maior que b, logo b$\leq$a e devemos retornar o valor de b.

Vale ressaltar que podemos fazer os parâmetros de uma função assumirem valores pré-definidos, quando não declarados na chamada. Se na declaração de $max$ tivéssemos usados os parâmetros "(int a, int b=0)", então a função saberia que, quando não a informássemos o valor de b, este devia ser zero. Ou seja, fazendo isso, ao chamarmos a função "max(x);" ela retornaria x se ele fosse positivo e 0 se ele não fosse, pois faria exatamente o mesmo de chamarmos "max(x, 0);". Para fazer isso, lembre-se que a função recebe os parâmetros na ordem em que foram declarados, portanto, não posso atribuir um valor "reserva" a um parâmetro se ainda houver parâmetros sem valores pré-definidos após ele ou salvar valores para dois parâmetros e deixar alguns sem valores salvos entre eles.

Para fixar ainda mais a ideia, tente escrever uma função que recebe um inteiro e retorna seu módulo (valor absoluto). Se não conseguir, segue o código, mas realmente tente fazê-la antes de lê-lo.

Recursividade

É importante saber que, dentro de uma função, podemos fazer qualquer coisa, exceto declarar outra função, como declarar e chamar variáveis, usar if e for e, até, chamar outras funções que já tenhamos declarado, inclusive ela mesma! Quando isso ocorre (uma função chama a si mesma), dizemos que é uma função recursiva. Recursão resolve uma infinidade de problema e é imprescindível que você saiba usá-la para fazer qualquer competição de informática. Grafos e Programação Dinâmica, que virão em aulas futuras, usam recursão na maioria de seus algoritmos.

Para entendermos melhor a ideia, vamos fazer o problema mais clássico de recurção, a função "int fib(int n)", que retornará o n-ésimo termo da Sequência de Fibonacci, onde n é não negativo. A primeira coisa que pensamos ao falar em recursividade é o que fazer para que a função não se chame infinitamente. Primeiro, temos que estabelecer um caso base, um certo tipo de entrada em que a função não usa a recursão, mas calcula o seu valor de retorno sem se chamar. No caso de Fibonacci, esse valores serão 0 e 1, pois sabemos que os dois primeiros termos da sequência (termo 0 e termo 1) são exatamente 0 e 1, respectivamente. Assim, a primeira linha da nossa função, antes de chamar a recursão, deve verificar se n $\leq$ 1, pois se for, deve retornar n. Feito isso, podemos chamar a recursão. Na sequência de Fibonacci, a partir do índice 2, um termo é a soma dos dois anteriores, ou seja, fib(n)=fib(n-1)+fib(n-2). Para implementar isso na função fazemos com que ela retorne essa soma, através do comando "return fib(n-1)+fib(n-2);". Segue o código de um programa que usa essa função para calcular o n-ésimo número de Fibonacci:

Outro ponto a ser notado quando usamos recursividade é garantir que em algum momento a recursão chegará nos casos base. No caso, note que n é sempre inteiro e a função sempre chama a recursão para valores menores que n, ou seja, ele vai sempre diminuindo e uma hora chegará em 1 ou em 0. São esses os dois pontos importantes: faça um caso base que retorne valor sem chamada recursiva e garanta que todos os outros casos irão caminhar para ele. Note que tivemos que fazer dois casos base (0 e 1) justamente porque a função chama a recursividade para dois valores (n-1 e n-2). Segue um ilustração para entendermos melhor o que acontece quando usamos recursão, usando o exemplo fib(5).

Observe, na ilustração, como as funções de cima vão chamando as de baixo e como elas sempre vão parar nos casos base, onde acaba a recursão pois a função retorna sem precisar chamar a recursividade, no caso em fib(1) e fib(0). O programa realiza estas chamadas sempre pela mais à esquerda primeiro, pois no código, repare que chamamos fib(n-1) antes de fib(n-2). Somando o resultado dos filhos na árvore de recursão, obtemos o resultado de determinada chamada da função.

Um outro exemplo de recursão é o Algoritmo de Euclides para determinação do MDC entre dois números. Se você não o conhece, clique aqui.

Resumindo, para encontrar o MDC(a, b), supondo sem perda de generalidade que a $\geq$ b, verifico:

1. Se a é múltiplo de b, MDC(a,b)=b;

2. Se não, MDC(a,b)=MDC(b, r), onde r é o resto que a deixa na divisão por b.

Você já conseguiu perceber como implementar a função recursiva? Já identificou o caso base e a recursividade? Enfim, tente fazer essa questão sozinho. Se não conseguir, seguem a explicação e o código abaixo.

Vamos criar a função recursiva "int mdc(int x, int y)", que receberá dois inteiros x e y como parâmetros e retornará o mdc entre eles. Vamos primeiro garantir que x é maior que y, trocando seus valores se ele não for. O caso base, em que a função retorna valor sem recursão ocorre quando x é múltiplo de y, ou seja, deixa resto zero na divisão por y, quando sabemos que y será o mdc entre eles. Em C++, lembre que o operador "%" é quem diz resto na divisão, ou seja, escreveremos, na função, o comando: "if(x%y==0) return y;"

Quando isso não ocorre, chamamos a recursão conforme diz o algoritmo, com o comando "return mdc(y, x%y);". Note que o resto da divisão de x por y é sempre menor que y, logo o segundo parâmetro vai sempre diminuindo, assim como o primeiro, pois ele será o menor entre os dois parâmetros da função que chamou a recursão (y$\leq$x). Como o y vai sempre diminuindo e é inteiro positivo, ele terá que chegar em um divisor de x, pois no pior dos casos chegará até 1, que divide qualquer inteiro positivo. Desse modo, a função sempre chegará nos casos base. Segue o código:

Veja, novamente a ilustração da recursão quando chamamos, no exemplo, mdc(756, 484):

Observe que, novamente, a função chama a recursão até chegar ao caso base mdc(28, 4), onde ela retorna 4 sem precisar de recursividade pois 4 é divisor de 28.

Agora que você já sabe de tudo isso, tente fazer os problemas listados abaixo. Se você tiver alguma dúvida ou dificuldade em algum problema, clique aqui para ir à pagina inicial do curso e preencher o formulário para tirar sua dúvida!

Problema 1 - The 3n+1 problem

Problema 2 - F91

Problema 3 - Fibonacci, Quantas Chamadass?

Problema 4 - Fatorial

Problema 5 - Brick Wall Patterns

Problema 6 - Investindo no Mercado de Ações 1

Problema 7 - The Coca-Cola Store

As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.