Exercicios Respondidos de Recursividade

Nome : Cristiano C. Duarte

1- Considere o m‚todo abaixo: public int X(int a)
{
if ( a 0; i--){ a+=i } return a;
}

A implementa‡Æo não recursiva tamb‚m seria O(n). Nesse caso, apesar das complexidades serem as mesmas,

c. Qual implementação é‚ mais eficiente? Justifique a fun‡Æo nÆo recursiva ‚ preferida por ser ,simples de implementar e nÆo necessitar de m£ltiplas chamadas de fun‡Æo (economia de mem¢ria e tempo). poss¡vel refazer essa fun‡Æo com um la‡o FOR,que ‚ mais economica que a versÆo recursiva,em termos de tempo e mem¢ria.

2- Seja a s‚rie de Fibonacci: 1,1,2,3,5,8,13,21,34,55, ... que pode ser definida recursivamente por: Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

Então escreva:
Uma função recursiva que gere o termo de ordem n da série de Fibonacci;

Um algoritmo que, utilizando a fun‡Æo definida acima gere a s‚rie de Fibonacci at‚ o termo de ordem 20.

public class Fibonacci {

static long fibo(int n) { if (n < 2) { return n; } else { return fibo(n - 1) + fibo(n - 2); } }

public static void main(String[] args) { for (int i = 0; i < 20; i++) { System.out.print("(" + i + "):" + Fibonacci.fibo(i) + "\t"); } }
}

3- Usando recursividade, calcule a soma de todos os valores de um array de n n£meros inteiros.

import java.util.*;

public class soma{ public static void main(String[] args){ int[] valores = new int[5]; // inicializa os elementos do array valores[0] = 23; valores[1] = 65; valores[2] = 2; valores[3] = 87; valores[4] = 34; // obt‚m a soma int soma = soma(valores); System.out.println("A soma dos valores ‚: " + soma); System.exit(0); }

public static int soma(int[] a){ int total = 0; for(int i = 0; i < a.length; i++){ total +=