Atividade De Algoritmos

EXERCÍCIOS PROPOSTOS

P11.01. Dê o conceito de recursividade.

P11.02. Quais as características dos problemas que são apropriados para serem resolvidos por recursão?

P11.03. Escreva uma função recursiva que calcule XN

, onde X é um número real e N é um inteiro não negativo. Essa

função pode ser definida da seguinte forma:

1.0 , se N = 0

X

N

=

X * XN-1

, se N > 0

P11.04. As séries de Fibonacci foram originalmente concebidas no século XIII por Leonardo de Pisa, apelidado de

Fibonacci, como um modelo para estudar a criação de coelhos. A aplicação desta série cresceu, não somente na

matemática e na ciência da computação, como também em vários fenômenos biológicos. A série em si é muito

simples: 0, 1, 1, 2, 3, 5, 8, 13, ... Os primeiros dois termos são 0 e 1; cada termo subseqüente é calculado como

a soma dos dois termos anteriores. Em geral, ti

= ti-1 + ti-2.

O problema de encontrar o enésimo número de Fibonacci tem uma formulação recursiva clara, que é:

Fibonacci (N-1) + Fibonacci (N-2) , se N > 2

Fibonacci (N) = 1 , se N = 2

0 , se N = 1

Escreva uma função recursiva em Pascal que, dado um valor N inteiro positivo, retorne o enésimo número de

Fibonacci.

P11.05. Um algoritmo muito conhecido para determinar o maior divisor comum de dois inteiros é o algoritmo de Euclides.

A função maior divisor comum (MDC) é definida como segue:

MDC (Y,X) , se Y > X

MDC (X,Y) = X , se Y = 0

MDC (Y, X mod Y) , se Y > 0

Construir uma função recursiva em Pascal para resolver este problema.

P11.06. Escreva uma versão não-recursiva da função abaixo:

function F (N:integer) : integer;

begin

if N > 1 then

F := N + F(N - 1)

else

F := 1

end;

P11.07. Escreva uma função recursiva que retorne a soma dos elementos de um vetor de elementos inteiros

(máx.de100). O tamanho do vetor também é passado como parâmetro.

P11.08. Escreva uma função recursiva que retorne a quantidade de números positivos de um vetor