Baixe o app para aproveitar ainda mais
Prévia do material em texto
Programação e Estruturas de Dados Jaqueline Faria de Oliveira Mestre em Informática E-mail: jaqueline.oliveira@prof.unibh.br Funções Recursivas Recursividade • Uma função pode chamar a si própria, e nestes casos essa função é chamada de função recursiva. – Atenção: Todo cuidado é pouco ao se fazer funções recursivas: • A primeira coisa a se providenciar é um critério de parada. Este vai determinar quando a função deverá parar de chamar a si mesma. Isto impede que a função se chame infinitas vezes. Recursividade • Três pontos devem ser lembrados quando construímos uma função recursiva: 1. Definir o problema em termos recursivos. 2. Definir um passo básico (ou mais) cujo resultado é imediatamente conhecido. 3. Cada vez que a função é chamada recursivamente, deve estar mais próxima de satisfazer a condição básica. Recursividade Exemplo: Função que calcula o fatorial de um número inteiro n com uma função recursiva: #include <stdio.h> int fatorial(int n){ if (n > 0) return n*fat(n-1); else return 1; } main(){ int n, fat; printf("\n\nDigite um valor para n: "); scanf("%d", &n); fat = fatorial(n); printf("\nO fatorial de %d e' %d", n, fat); } Recursividade • Função que calcula o fatorial de um número inteiro n com uma função recursiva. • Note que, enquanto n não for igual a 0, a função fat chama a si mesma, cada vez com um valor menor. • Quando n=0 a função para sua execução. Recursividade • Para entender o funcionamento de uma função recursiva podemos imginar da seguinte forma: – A cada nova chamada recursiva uma outra função idêntica é chamada. • O que ocorre na memória é quase a mesma coisa. Recursividade Exemplo: Uma chamada de fatorial onde n = 3: n = 3 int fatorial(int n){ if (3 > 0) return n*fat(3-1); else return 1; } n = 2 int fatorial(int n){ if (2 > 0) return n*fat(2-1); else return 1; } n = 1 int fatorial(int n){ if (1 > 0) return n*fat(1-1); else return 1; } n = 0 int fatorial(int n){ return 1; } Recursividade • Há certos algoritmos que são mais eficientes quando feitos de maneira recursiva, mas a recursividade é algo a ser evitado sempre que possível, pois, se usada incorretamente, tende a consumir muita memória e ser lenta. • Lembre-se que memória é consumida cada vez que o computador faz uma chamada a uma função. Com funções recursivas a memória do computador pode se esgotar rapidamente. Exercícios 1. Crie uma função recursiva que receba um número inteiro positivo N e calcule o somatório dos números de 1 a N. 2. Faça uma função recursiva que receba um número inteiro positivo N e imprima todos os números naturais de 0 até N em ordem crescente. 3. Crie um programa em C, que contenha uma função recursiva que receba dois inteiros positivos k e n e calcule kn. Utilize apenas multiplicações. O programa principal deve solicitar ao usuário os valores de k e n e imprimir o resultado da chamada da função. Exercícios 1. Crie uma função recursiva que receba um número inteiro positivo N e calcule o somatório dos números de 1 a N. Exercícios 2. Faça uma função recursiva que receba um número inteiro positivo N e imprima todos os números naturais de 0 até N em ordem crescente. Referências • C Completo e Total. Terceira edição. Herbert Schildt. Editora Pearson. • Notas de aula professor Walisson Ferreira. • Programação e Estruturas de Dados em Linguagem C (PED). Pollyanna Miranda de Abreu.
Compartilhar