"Indutivamente" e "recursivamente" têm significados muito semelhantes?

11

"Indutivamente" e "recursivamente" significam muito semelhantes?

Por exemplo, se existe um algoritmo que determina um vetor n-dim determinando seus primeiros componentes k + 1 com base em seus primeiros k componentes que foram determinados e é inicializado com o primeiro componente, você chamaria de trabalho recursivo ou indutivo? Eu tenho usado "recursivamente", mas hoje alguém disse "indutivamente".

Tim
fonte
Este artigo sobre Indução e recursão resume bem, mas a essência é que eles estão intimamente relacionados; uma prova de indução matemática pode ser escrita como um algoritmo recursivo.
Merbs 23/10/12
Indutivamente, geralmente significa recursivamente de a , então recursivamente é o advérbio mais geral. n + 1nn+1
Yuval Filmus
Que tipo de recursividade não é indutivamente, @YuvalFilmus?
Tim
@YuvalFilmus: Essa é uma noção muito limitada de indutivo.
23412 Dave Clarke
Para mim, eles significam a mesma coisa fora de contexto. Em um contexto específico, eles podem significar coisas diferentes.
Gilles 'SO- stop be evil' (

Respostas:

6

Não , mas não pelas razões que outras pessoas deram. A diferença entre recursão e indução não é que a recursão seja "de cima para baixo" e a indução seja "de baixo para cima". A indução é isomórfica para algo chamado "recursão primitiva", mas, em geral, a recursão é estritamente mais poderosa que a indução .

A distinção entre descendente e descendente é trivial - qualquer programa recursivo primitivo "descendente" pode ser mecanicamente convertido em algo "descendente". De fato, qualquer prova por indução pode ser transformada em um programa recursivo. Na estrutura do cálculo das construções indutivas, se você quiser provar que todo número natural é esbelto, você o escreveria como uma função que constrói uma prova de que n é esbelto, fazendo uma chamada recursiva para construir uma prova que n- 1 é enganoso.

O fator-chave da indução é que as coisas são definidas em termos de coisas menores e elas "atingem o fundo do poço" após finitas etapas. Os números naturais são indutivos porque todo natural é 0 ou o sucessor de um natural menor. As listas são indutivas porque todas as listas estão vazias ou podem ser divididas ("desdobradas") em um elemento e em uma lista menor.

Às vezes, programas recursivos não são escritos em termos de coisas menores. Por exemplo, considere esta função da Collatz:

fun collatz(n) 
   if n <= 1
      return 0;
   else if n % 2 == 0
     return 1 + collatz(n / 2)
   else
     return 1 + collatz(3 * n + 1)
end

Essa função não é de cima para baixo nem de baixo para cima e, portanto, não é indutiva sobre os números naturais.

Pode haver uma ordem para tratar isso indutivamente, mas para a maioria das coisas simplesmente não há como. Funções sobre fluxos infinitos são um ótimo exemplo. De fato, os fluxos são o exemplo prototípico de um tipo "coindutor".

O livro "Fundamentos práticos para linguagens de programação", de Bob Harper, disponível on-line gratuitamente, apresenta uma boa introdução aos tipos indutivo, coindutor e recursivo.

James Koppel
fonte
2

Para mim, é principalmente uma questão de ponto de vista. Se eu definir objetos com base em objetos menores, faço-o indutivamente, de modo que seja de baixo para cima. Se eu resolver um problema, decompondo-o em pedaços menores resolvidos da mesma maneira que chamo de recursão, isso é de cima para baixo.

(editar) PS. Veja uma pergunta semelhante em nosso departamento irmão de Matemática, definição recursiva vs. indutiva . Cito a resposta de Carl Mummert:

Minha melhor descrição é que "definição indutiva" é mais comum quando definimos um conjunto de objetos "do nada", enquanto "definição recursiva" é mais comum quando definimos uma função em uma coleção de objetos já existente.

Mas mais importante:

não vale a pena perder o sono

Hendrik Jan
fonte
então "recursão = dividir e conquistar", qual primeiro de cima para baixo e depois de baixo para cima?
Tim
1

Não, eles não são os mesmos. E você está certo (eu estou assumindo sobre o algoritmo que você está descrevendo): é recursivo.

O motivo é a definição de ambas as palavras, que você pode ler em um dicionário ou Wikipedia.

A indução (assumindo "indução matemática") é especificamente sobre provar que todos os casos de um argumento são verdadeiros.

A recursão é especificamente sobre um processo que talvez esteja sendo repetido de alguma forma no mesmo processo.

RE: respostas de outras pessoas:

Depois de ver as respostas de outras pessoas, entendo por que há confusão: ao definir estruturas de dados, funções e linguagens, alguns teóricos parecem usar 'indutivo' e 'recursivo' de uma maneira confusa (ver comentários a esta pergunta). Não acho que a resposta de Koppel (mesmo com os votos mais altos atualmente) reflita realmente essa confusão. Já que estamos falando de um algoritmo, eu não diria que existem 'algoritmos indutivos'; Eu acho que é uma categorização desnecessária.

Tom
fonte
A indução não é apenas uma prova. Você também usá-lo o tempo todo para definir indutivamente estruturas recursivas (estruturas de dados, linguagens, etc.)
hugomg
@missingno Forneça uma fonte para essa definição.
Tom
Um exemplo que eu poderia pensar é aqui : "A linguagem de \ mathcal {L}, também conhecido como seu conjunto de fórmulas, fórmulas ou fbfs bem formado, é indutivamente definido pelas seguintes regras:"
hugomg
@missingno que leva a esta Wikipedia página onde eu acho que há um redundante e uso confuso da palavra 'indutivo', essencialmente sendo usado como 'recursiva'
Tom
Por favor, não me faça procurar mais exemplos. Mesmo que você não concorde com isso, é definitivamente um idioma muito comum e você pode encontrá-lo em muitos livros também, se o procurar. E não é como se alguém editou o artigo da Wikipedia com o propósito de provar o meu ponto ...
hugomg