O que é tão difícil sobre ponteiros / recursão? [fechadas]

20

Nos perigos das escolas java, Joel discute sua experiência na Penn e a dificuldade de "falhas de segmentação". Ele diz

[Segfaults são difíceis até que você] "respire fundo e realmente tente forçar sua mente a trabalhar em dois níveis diferentes de abstração simultaneamente".

Dada uma lista de causas comuns para segfaults, não entendo como precisamos trabalhar em dois níveis de abstração.

Por alguma razão, Joel considera esses conceitos essenciais para a capacidade de abstração dos programadores. Não quero assumir demais. Então, o que é tão difícil sobre ponteiros / recursão? Exemplos seria bom.

P.Brian.Mackey
fonte
31
Pare de se preocupar com o que Joel pode pensar de você. Se você acha fácil recursão, isso é bom. Nem todo mundo faz.
FrustratedWithFormsDesigner
6
A recursão é fácil por definição (função que chama a si mesma), mas saber quando usá-lo e como fazê-lo funcionar é a parte mais difícil.
Jeffo
9
Candidate-se a um emprego na Fog Creek e informe-nos como é. Estamos todos muito interessados ​​em sua autopromoção.
Joel Etherton
4
@ P.Brian.Mackey: Não estamos entendendo mal. A pergunta realmente não pergunta nada. É flagrante autopromoção. Se você quer saber o que Joel está perguntando sobre ponteiros / recursão, perguntar-lhe: [email protected]
Joel Etherton
19
Duplicado desta pergunta ?
ozz

Respostas:

38

Percebi pela primeira vez que os indicadores e a recursão eram difíceis na faculdade. Eu tinha participado de alguns cursos típicos do primeiro ano (um era C e Assembler, o outro era no Scheme). Ambos os cursos começaram com centenas de estudantes, muitos dos quais tinham anos de experiência em programação no ensino médio (normalmente BASIC e Pascal, naqueles dias). Porém, assim que os indicadores foram introduzidos no curso C e a recursão foi introduzida no esquema, um grande número de estudantes - talvez até a maioria - ficou completamente confuso. Eram crianças que escreveram MUITO código antes e não tiveram nenhum problema, mas quando atingiram os indicadores e a recursão, também atingiram uma parede em termos de capacidade cognitiva.

Minha hipótese é que indicadores e recursão são os mesmos, pois exigem que você mantenha dois níveis de abstração em sua cabeça ao mesmo tempo. Há algo sobre os múltiplos níveis de abstração que requer um tipo de aptidão mental que é muito possível que algumas pessoas nunca terão.

  • Com ponteiros, os "dois níveis de abstração" são "dados, endereço de dados, endereço de endereço de dados etc." ou o que tradicionalmente chamamos de "valor versus referência". Para o aluno não treinado, é muito difícil ver a diferença entre o endereço de x e o próprio x .
  • Com a recursão, os "dois níveis de abstração" estão entendendo como é possível uma função se chamar. Às vezes, um algoritmo recursivo é o que as pessoas chamam de "programação por pensamento positivo" e é muito, muito natural pensar em um algoritmo em termos de "caso base + caso indutivo", em vez da lista mais natural de etapas que você segue para resolver um problema . " Para o aluno não treinado que olha para um algoritmo recursivo, o algoritmo parece pedir a pergunta .

Eu também estaria perfeitamente disposto a aceitar que é possível ensinar sugestões e / ou recursões a alguém ... Eu não tenho nenhuma evidência de uma maneira ou de outra. Eu sei que, empiricamente, ser capaz de realmente entender esses dois conceitos é um bom preditor da capacidade geral de programação e que, no curso normal do treinamento de graduação em CS, esses dois conceitos permanecem como alguns dos maiores obstáculos.

Joel Spolsky
fonte
4
"muito, muito antinatural pensar em um algoritmo em termos de" caso base + caso indutivo "" - acho que não é antinatural, apenas que as crianças não estão sendo treinadas de acordo.
Ingo
14
se fosse natural, você não precisaria ser treinado. : P
Joel Spolsky
1
Bom ponto :), mas não precisamos de treinamento em matemática, lógica, física etc. todos os quais, em um sentido mais amplo, são mais naturais. Curiosamente, poucos programadores têm problemas com a sintaxe das linguagens, mas ela é cheia de recursão.
Ingo
1
Na minha universidade, o primeiro curso começou com programação funcional e recursão quase imediatamente, bem antes de introduzir mutação e coisas do gênero. Descobri que alguns dos estudantes sem experiência entendiam melhor a recursão do que aqueles com alguma experiência. Dito isto, o topo da classe era formado por pessoas com muita experiência.
Tikhon Jelvis
2
Eu acho que a incapacidade de entender indicadores e recursão está ligada a) nível geral de QI eb) má educação matemática.
quant_dev
23

A recursão não é apenas "uma função que se chama". Você realmente não vai entender por que a recursão é difícil até que você se encontre desenhando quadros de pilha para descobrir o que deu errado com seu analisador de descida recursiva. Freqüentemente, você terá funções recursivas mutuamente (a função A chama a função B, que chama a função C, que pode chamar a função A). Pode ser muito difícil descobrir o que deu errado quando você está N quadros de pilha em uma série de funções mutuamente recursivas.

Quanto aos ponteiros, novamente, o conceito de ponteiros é bastante simples: uma variável que armazena um endereço de memória. Porém, novamente, quando algo dá errado com sua complicada estrutura de dados de void**ponteiros que apontam para nós diferentes, você verá por que isso pode ficar complicado quando você tenta descobrir por que um de seus ponteiros está apontando para um endereço de lixo.

Charles Salvia
fonte
1
A implementação de um analisador decente recursivo foi quando realmente senti que tinha um certo domínio sobre a recursão. Os ponteiros são fáceis de entender em alto nível, como você disse; não é até você entender os detalhes das implementações que lidam com os ponteiros que você percebe por que eles são complicados.
Chris
A recursão mútua entre muitas funções é essencialmente a mesma que goto.
starblue
2
@ starblue, na verdade não - já que cada stackframe cria novas instâncias de variáveis ​​locais.
22611 Charles Salvia
Você está certo, apenas a recursão da cauda é igual a goto.
starblue
3
O @wnoise int a() { return b(); }pode ser recursivo, mas depende da definição de b. Por isso não é tão simples como parece ...
alternativa
14

Java suporta ponteiros (eles são chamados de referências) e suporta recursão. Então, na superfície, seu argumento parece inútil.

O que ele está realmente falando é a capacidade de depurar. Um ponteiro Java (err, referência) é garantido para apontar para um objeto válido. Ponteiro AC não é. E o truque na programação C, supondo que você não use ferramentas como o valgrind , é descobrir exatamente onde você errou um ponteiro (raramente é no ponto encontrado em um rastreamento de pilha).

Anon
fonte
5
Ponteiros em si são um detalhe. Usar referências em Java não é mais complicado do que usar variáveis ​​locais em C. Mesmo misturá-las da maneira que as implementações de Lisp (um átomo pode ser um número inteiro de tamanho limitado, um caractere ou um ponteiro) não é difícil. Torna-se mais difícil quando o idioma permite que o mesmo tipo de dados seja local ou referenciado, com sintaxe diferente, e muito peludo quando o idioma permite aritmética de ponteiro.
21711 David Thornley
@ David - hum, o que isso tem a ver com a minha resposta?
Anon
1
Seu comentário sobre ponteiros de suporte Java.
precisa
"onde você estragou um ponteiro (raramente é no ponto encontrado em um rastreamento de pilha)." Se você tiver sorte o suficiente para obter um rastreamento de pilha.
Omega Centauri
5
Eu concordo com David Thornley; Java não suporta ponteiros, a menos que eu possa fazer um ponteiro para um ponteiro para um ponteiro para um ponteiro para um int. O que talvez eu suponha que poderia, criando entre 4 e 5 classes, cada uma com outra referência, mas isso é realmente uma indicação ou é uma solução feia?
alternativa
12

O problema com ponteiros e recursão não é necessariamente difícil de entender, mas é ensinado mal, principalmente no que diz respeito a idiomas como C ou C ++ (principalmente porque os próprios idiomas estão sendo mal ensinados). Toda vez que ouço (ou leio) alguém diz "uma matriz é apenas um ponteiro", morro um pouco por dentro.

Da mesma forma, toda vez que alguém usa a função Fibonacci para ilustrar a recursão, quero gritar. É um péssimo exemplo, porque a versão iterativa não é mais difícil de escrever e apresenta um desempenho tão bom ou melhor que o recursivo, e não fornece uma visão real sobre por que uma solução recursiva seria útil ou desejável. Quicksort, travessia de árvore, etc., são exemplos muito melhores do porquê e como da recursão.

Ter que mexer com ponteiros é um artefato de trabalhar em uma linguagem de programação que os expõe. Gerações de programadores do Fortran estavam construindo listas, árvores, pilhas e filas sem precisar de um tipo de ponteiro dedicado (ou alocação dinâmica de memória), e nunca ouvi alguém acusar o Fortran de ser uma linguagem de brinquedo.

John Bode
fonte
Eu concordo, eu tinha anos / décadas de Fortran antes de ver indicadores reais, então eu já estava usando minha própria maneira de fazer a mesma coisa, antes de ter a chance de deixar que a linguagem / compilador fizesse isso por mim. Também acho que a sintaxe C em relação aos ponteiros / endereços é muito confusa, embora o conceito de valor armazenado em um endereço seja muito simples.
Omega Centauri
se você tiver um link para o Quicksort implementado no Fortran IV, eu adoraria vê-lo. Não estou dizendo que isso não pode ser feito - de fato, eu o implementei no BASIC há cerca de 30 anos -, mas eu estaria interessado em vê-lo.
Anónimo
Eu nunca trabalhei no Fortran IV, mas implementei alguns algoritmos recursivos na implementação do Fortran 77 VAX / VMS (havia um gancho para permitir que você salvasse o alvo de um goto como um tipo especial de variável, para que você pudesse escrever GOTO target) . Acho que tivemos que criar nossas próprias pilhas de tempo de execução. Isso foi há tempo suficiente para eu não me lembrar mais dos detalhes.
John Bode
8

Existem várias dificuldades com os ponteiros:

  1. Alias A possibilidade de alterar o valor de um objeto usando diferentes nomes / variáveis.
  2. Não localidade A possibilidade de alterar o valor de um objeto em um contexto diferente daquele em que é declarado (isso também ocorre com argumentos passados ​​por referência).
  3. Incompatibilidade da vida útil A vida útil de um ponteiro pode ser diferente da vida útil do objeto para o qual ele aponta e pode levar a referências inválidas (SEGFAULTS) ou lixo.
  4. Aritmética do ponteiro . Algumas linguagens de programação permitem a manipulação de ponteiros como números inteiros, e isso significa que os ponteiros podem apontar para qualquer lugar (incluindo os locais mais inesperados quando um bug está presente). Para usar a aritmética dos ponteiros corretamente, um programador deve estar ciente dos tamanhos de memória dos objetos apontados, e isso é algo mais a se pensar.
  5. Conversões de tipo A capacidade de converter um ponteiro de um tipo para outro permite substituir a memória de um objeto diferente daquele que se destina.

É por isso que um programador deve pensar mais profundamente ao usar ponteiros (não sei sobre os dois níveis de abstração ). Este é um exemplo dos erros típicos cometidos por um novato:

Pair* make_pair(int a, int b)
{
    Pair p;
    p.a = a;
    p.b = b;
    return &p;
}

Observe que códigos como o acima são perfeitamente razoáveis ​​em linguagens que não têm um conceito de ponteiros, mas um nome (referências), objetos e valores, como linguagens de programação funcionais e linguagens com coleta de lixo (Java, Python). .

A dificuldade com funções recursivas ocorre quando pessoas sem formação matemática suficiente (onde a recursividade é comum e requer conhecimento) tentam abordá-las pensando que a função se comportará de maneira diferente dependendo de quantas vezes ela foi chamada anteriormente . Esse problema é agravado porque as funções recursivas podem realmente ser criadas de maneiras pelas quais você precisa pensar dessa maneira para entendê-las.

Pense em funções recursivas com ponteiros sendo distribuídos, como em uma implementação processual de uma Árvore Vermelho-Preta na qual a estrutura de dados é modificada no local; é algo mais difícil de pensar do que uma contraparte funcional .

Não é mencionado na pergunta, mas a outra questão importante com a qual os novatos têm dificuldade é a simultaneidade .

Como outros já mencionaram, há um problema adicional, não conceitual, em algumas construções da linguagem de programação: é que, mesmo que entendamos, erros simples e honestos com essas construções podem ser extremamente difíceis de depurar.

Apalala
fonte
O uso dessa função retornará um ponteiro válido, mas a variável está em um escopo maior que o escopo que chamou a função; portanto, o ponteiro pode (suponha que será) invalidado quando o malloc estiver sendo usado.
rightfold
4
@Radek S: Não, não vai. Ele retornará um ponteiro inválido que, em alguns ambientes, funciona por um tempo até que outra coisa o substitua. (Na prática, esta será a pilha, não a pilha. malloc()Não é mais provável do que qualquer outra função para fazer isso.)
wnoise
1
@Radeck Na função de amostra, o ponteiro aponta para a memória que a linguagem de programação (C neste caso) garante será liberada assim que a função retornar. Assim, o ponteiro retornado aponta para o lixo . Os idiomas com coleta de lixo mantêm o objeto ativo, desde que seja referenciado em qualquer contexto.
Apalala
A propósito, Rust tem indicadores, mas sem esses problemas. (quando não estiver em contexto inseguro)
Sarge Borsch
2

Ponteiros e recursão são dois animais separados e existem diferentes razões que qualificam cada um deles como "difícil".

Em geral, os ponteiros requerem um modelo mental diferente da atribuição pura de variáveis. Quando tenho uma variável de ponteiro, é apenas isso: um ponteiro para outro objeto, os únicos dados que ele contém são o endereço de memória para o qual apontam. Por exemplo, se eu tenho um ponteiro int32 e atribui um valor diretamente a ele, não estou alterando o valor do int, estou apontando para um novo endereço de memória (há muitos truques legais que você pode fazer com isso ) Ainda mais interessante é ter um ponteiro para um ponteiro (é o que acontece quando você passa uma variável Ref como uma função Parâmetro em C #, a função pode atribuir um objeto totalmente diferente ao Parâmetro e esse valor ainda estará no escopo quando a função saídas.

A recursão dá um pequeno salto mental na primeira aprendizagem, porque você define uma função em termos de si mesma. É um conceito selvagem quando você se depara com ele, mas depois de entender a idéia, ela se torna uma segunda natureza.

Mas voltando ao assunto em questão. O argumento de Joel não é sobre indicadores ou recursão por si só, mas o fato de os alunos estarem sendo mais afastados de como os computadores realmente funcionam. Esta é a ciência em ciência da computação. Há uma diferença distinta entre aprender a programar e aprender como os programas funcionam. Eu não acho que seja uma questão de "eu aprendi dessa maneira, para que todos tenham que aprender dessa maneira", como ele argumentando que muitos programas de CS estão se tornando escolas de comércio glorificadas.

Michael Brown
fonte
1

Dou a P. Brian um +1, porque sinto que ele faz: recursão é um conceito tão fundamental que quem tem as menores dificuldades com ele deve considerar procurar um emprego na mac donalds, mas, mesmo assim, existe recursão:

make a burger:
   put a cold burger on the grill
   wait
   flip
   wait
   hand the fried burger over to the service personel
   unless its end of shift: make a burger

Certamente, a falta de compreensão também tem a ver com nossas escolas. Aqui deve-se introduzir números naturais como Peano, Dedekind e Frege, para que não tenhamos tantas dificuldades mais tarde.

Ingo
fonte
6
Isso é recusão de cauda, ​​que é indiscutivelmente repetida.
Michael K
6
Desculpe, para mim, looping é indiscutivelmente recursão de cauda :)
Ingo
3
@ Ingo: :) Fanático funcional!
Michael K
1
@ Michael - hehe, de fato !, mas acho que podemos argumentar que recursão é o conceito mais fundamental.
Ingo
@ Ingo: Você poderia, de fato (seu exemplo demonstra isso bem). No entanto, por algum motivo, os seres humanos têm dificuldade com isso na programação - parecemos querer isso extra goto toppor algum motivo, IME.
Michael K
1

Eu discordo de Joel de que o problema é pensar em vários níveis de abstração per se, acho que os indicadores e a recursão são dois bons exemplos de problemas que exigem uma mudança no modelo mental que as pessoas têm de como os programas funcionam.

Acho que os ponteiros são o caso mais simples para ilustrar. Lidar com ponteiros requer um modelo mental de execução de programa que explique como os programas funcionam de fato com endereços e dados de memória. Minha experiência foi que muitas vezes os programadores nem pensam nisso antes de aprenderem sobre ponteiros. Mesmo que o conheçam em um sentido abstrato, não o adotaram em seu modelo cognitivo de como um programa funciona. Quando os ponteiros são introduzidos, é necessária uma mudança fundamental na maneira como eles pensam sobre como o código funciona.

A recursão é problemática porque existem dois blocos conceituais para a compreensão. O primeiro está no nível da máquina e, assim como os indicadores, pode ser superado através do desenvolvimento de um bom entendimento de como os programas são realmente armazenados e executados. O outro problema com a recursão é, penso eu, que as pessoas têm uma tendência natural de tentar desconstruir um problema recursivo em um não recursivo, o que atrapalha a compreensão de uma função recursiva como gestalt. Isso é um problema com pessoas com formação matemática insuficiente ou um modelo mental que não vincula a teoria matemática ao desenvolvimento de programas.

O fato é que não acho que indicadores e recursão sejam as únicas duas áreas problemáticas para pessoas presas em um modelo mental insuficiente. O paralelismo parece ser outra área em que algumas pessoas simplesmente ficam presas e têm dificuldade em adaptar seu modelo mental para dar conta, é apenas que muitas vezes é fácil testar indicadores e recursões em uma entrevista.

Cercerilla
fonte
1
  DATA    |     CODE
          |
 pointer  |   recursion    SELF REFERENTIAL
----------+---------------------------------
 objects  |   macro        SELF MODIFYING
          |
          |

O conceito de dados e códigos auto-referenciais está subjacente à definição de ponteiros e recursão, respectivamente. Infelizmente, a ampla exposição a linguagens de programação imperativas levou os estudantes de ciência da computação a acreditar que precisam entender a implementação através do comportamento operacional de seus tempos de execução, quando devem confiar esse mistério no aspecto funcional da linguagem. Somar todos os números até cem parece uma simples questão de começar com um e adicioná-lo ao próximo na sequência e fazê-lo ao contrário com o auxílio de funções circulares de auto-referência parece perverso e até perigoso para muitos não acostumados à segurança de funções puras.

O conceito de dados e códigos auto-modificativos está subjacente à definição de objetos (dados inteligentes) e macros, respectivamente. Menciono isso porque eles são ainda mais difíceis de entender, especialmente quando é esperado um entendimento operacional do tempo de execução a partir de uma combinação dos quatro conceitos - por exemplo, uma macro que gera um conjunto de objetos que implementa um analisador decente recursivo com a ajuda de uma árvore de ponteiros . Em vez de rastrear a operação inteira do estado do programa passo a passo através de cada camada de abstração de uma só vez, os programadores imperativos precisam aprender a confiar que suas variáveis ​​são atribuídas apenas uma vez dentro de funções puras e que invocações repetidas da mesma função pura com os mesmos argumentos sempre produzem o mesmo resultado (ou seja, transparência referencial), mesmo em uma linguagem que também suporta funções impuras, como Java. Correr em círculos após o tempo de execução é um esforço infrutífero. Abstração deve simplificar.

Não competitivo
fonte
-1

Muito parecido com a resposta de Anon.
Além das dificuldades cognitivas para iniciantes, os indicadores e a recursão são muito poderosos e podem ser usados ​​de maneiras enigmáticas.

A desvantagem do grande poder é que eles oferecem grande poder para estragar seu programa de maneiras sutis.
Armazenar um valor falso em uma variável normal já é ruim o suficiente, mas armazenar algo falso em um ponteiro pode causar todos os tipos de coisas catastróficas atrasadas.
E pior, esses efeitos podem mudar à medida que você tenta diagnosticar / depurar qual é a causa do comportamento bizarro do programa.

Da mesma forma com recursão. Pode ser uma maneira muito poderosa de organizar coisas complicadas - colocando as coisas complicadas na estrutura de dados ocultos (pilha).
Mas, se algo for feito sutilmente errado, pode ser difícil descobrir o que está acontecendo.

Omega Centauri
fonte