71 pág.

Pré-visualização | Página 2 de 2
Exercício int MDC (int n, int m) { if ( (n>=m) && ((n%m)==0) ) return(m); else { } } 44 Exercício int MDC (int n, int m) { if ( (n>=m) && ((n%m)==0) ) return(m); else { if (n<m) return (MDC(m,n)); } } 45 Exercício int MDC (int n, int m) { if ( (n>=m) && ((n%m)==0) ) return(m); else { if (n<m) return (MDC(m,n)); else return (MDC(m,n%m)); } } 46 Exercício 1) Faça um procedimento recursivo que receba dois valores inteiros a e b e imprima o intervalo fechado entre eles. Se a for maior que b mostrar mensagem de erro. 2) Faça o teste de mesa do procedimento abaixo e informe qual será a saída do mesmo se a chamada for faz( 1, 4 ). faz (inteiro a, inteiro b) { se (a <= b) { faz ( a + 1, b); imprime( a ); } } 47 Exercício 3) Dada a função X: int X (int n, int m) { if ((n<=m) || (m==0) || (n==0)) return 1; return X(n-1,m)+X(n-1,m+1); } a) Qual o valor de X(5,3) ? b) Quantas chamadas serão feitas na avaliação acima? 48 Exercícios 4) Escreva uma função recursiva para calcular o somatório dos N primeiros números inteiros positivos. 5) Escreva uma função recursiva que recebe como parâmetros um número real X e um inteiro N e retorna o valor de XN. Obs.: N pode ser negativo 6) Escreva uma função recursiva para determinar o número de dígitos de um número N inteiro. Recursividade DCC120 Laboratório de Programação 50 Definição � Uma função é dita recursiva quando chama a si própria, direta ou indiretamente. � Propósito: expressar sua funcionalidade ou objetivo de maneira mais clara e concisa. � Linguagens que permitem uma função chamar a si própria são ditas recursivas � A linguagem C é uma linguagem recursiva. 51 Exemplo de Algoritmo recursivo Cálculo do valor de 2n para um número n: Aprendemos que 2n = 2 * 2 * 2 * D * 2. 52 Exemplo de Algoritmo recursivo Implementação iterativa muito simples: int Potencia(int n) { int Pot, i; Pot = 1; for (i = 1; i <= n; i++) Pot = Pot * 2; return (Pot); } 53 Calcular o valor de 2n como sendo 2 * 2n-1: 2, se n = 1 2n 2 * 2n-1, se n > 1 Exemplo de Algoritmo recursivo 54 Exemplo de Algoritmo recursivo � Significa que, para cálculo do valor de 2n para um determinado n, há necessidade de que se recorra aos cálculos anteriores. Por exemplo: Quanto é o 24? 55 24 24 = Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 56 24 24 = 2 * 23 Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 57 24 24 = 2 * 23 23 = Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 58 24 24 = 2 * 23 23 = 2 * 22 Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 59 24 24 = 2 * 23 23 = 2 * 22 22 = Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 60 24 24 = 2 * 23 23 = 2 * 22 22 = 2 * 21 Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 61 24 24 = 2 * 23 23 = 2 * 22 22 = 2 * 21 21 = Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 62 24 24 = 2 * 23 23 = 2 * 22 22 = 2 * 21 21 = 2 Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 63 24 24 = 2 * 23 23 = 2 * 22 22 = 2 * 21 = 2 * 2 = 4 21 = 2 Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 64 24 24 = 2 * 23 23 = 2 * 22 = 2 * 4 = 8 22 = 2 * 21 = 2 * 2 = 4 21 = 2 Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 65 24 24 = 2 * 23 = 2 * 8 = 16 23 = 2 * 22 = 2 * 4 = 8 22 = 2 * 21 = 2 * 2 = 4 21 = 2 Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 66 24 24 = 2 * 23 = 2 * 8 = 16 23 = 2 * 22 = 2 * 4 = 8 22 = 2 * 21 = 2 * 2 = 4 21 = 2 Portanto, 24 = 16 Exemplo de Algoritmo recursivo 2, se n = 1 2n 2 * 2n-1, se n > 1 67 � Condição que define parada da recursão: chamada base da recursão ou de caso base � Todo programa recursivo deve possuir uma condição de parada ! � Condição que define recursão chamada passo recursivo. Exemplo de Algoritmo recursivo 68 2, se n = 1 Base da recursão 2n 2 * 2n-1, se n > 1 Passo recursivo Exemplo de Algoritmo recursivo 69 int PotenciaRecursivo (int n) { if (n == 1) Base da recursão return (2); else return (2 * PotenciaRecursivo (n - 1)); } Passo recursivo Exemplo de Algoritmo recursivo 70 Exercícios 1) Escreva uma função recursiva para calcular o N-ésimo número da sequência de Fibonacci. A sequência é dada por: 2) Seja S um vetor de inteiros. Descreva funções recursivas para calcular: a) o elemento máximo de S; b) a soma dos elementos de S; c) média aritmética dos elementos de S. 3) Escreva um procedimento recursivo que imprima na tela os números ímpares de 1 à um número fornecido pelo usuário. 71 Exercícios 4) Escreva um procedimento recursivo, ImprimeSerie (i, j, k), que imprime na tela a série de valores do intervalo [i,j], com incremento k (i, j e k são inteiros). 5) Escreva uma função recursiva int SomaSerie (i, j, k), que devolva a soma da série de valores do intervalo [i,j], com incremento k (i, j e k são inteiros). 6) Faça uma função recursiva que calcule o valor da série S descrita a seguir para um valor n > 0 a ser fornecido como parâmetro para a mesma: S = 1 + 1/2! + 1/3! + ... 1/n! OBS: A função fatorial também deve ser recursiva.