Ine5403 Fundamentos de Matemática Discreta para a Computação 3 Indução e Recursão


Download 444 b.
Sana14.08.2018
Hajmi444 b.


INE5403 - Fundamentos de Matemática Discreta para a Computação

  • 3) Indução e Recursão

  • 3.1) Indução Matemática

  • 3.2) Indução Forte

  • 3.3) Definições Recursivas (funções, conjuntos, estruturas)

  • 3.4) Indução Estrutural

  • 3.5) Algoritmos Recursivos


Definições recursivas

  • Algumas vezes pode ser difícil definir um objeto explicitamente, mas pode ser fácil defini-lo recursivamente, incluindo o item que está sendo definido como parte da definição.



Funções definidas recursivamente

  • Exemplo:

  • f(0) = 3 f(n+1) = 2.f(n) + 3

  • Encontre f(1), f(2), f(3) e f(4).



Funções definidas recursivamente

  • Exemplo (função fatorial): Forneça uma definição recursiva da função fatorial F(n) = n! .



Algoritmos definidos recursivamente

  • Exemplo: suponha uma seqüência definida como: 1. S1 = 2 2. Sn = 2.Sn-1 para n2



Algoritmos definidos recursivamente

  • Exemplo(cont.): suponha uma seqüência definida como: 1. S1 = 2 2. Sn = 2.Sn-1 para n2



Algoritmos definidos recursivamente

  • Exemplo: construa uma versão recursiva do algoritmo de busca binária, usado para localizar um valor x em uma seqüência a1,a2,...,an.




Do'stlaringiz bilan baham:


Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2017
ma'muriyatiga murojaat qiling