Fórum Problema com recursividade (Stack OverFlow) #254185
13/10/2004
0
Os dados de entrada são uma imagem(onde pixel preto é parede, e branco espaço livre), e o ponto de partida (onde
estou no labirinto em coordenadas de pixel). O algoritmo percorre a imagem recusivamente, guardando num vetor
os pixels de parede. Se ele acha uma parede, ele não a transpassa.
O algoritmo funciona perfeitamente bem para imagens pequenas, mas para maiores, dá stack overflow.
Haveria uma maneira de resolver esse problema?
Deveria ser feito um algoritmo sem recursividade, sendo impossivel conseguir o resultado desejado com recursividade?
Como poderia ser feito então?
Preciso resolver isso com certa urgência, se alguém ja fez alguma coisa similar e puder me ajudar, agradeço.
[b:c90b05fb38]Título editado: removido ´ - URGENTE!´[/b:c90b05fb38]
Sandra/Moderação
Gabriela
Curtir tópico
+ 0Posts
13/10/2004
Rômulo Barros
Gostei + 0
13/10/2004
Vinicius2k
Colega Gabriela,
Neste tópico ocorreu infração às Regras de Conduta do Fórum :
[list:0ff7aa71e2][*:0ff7aa71e2]Utilização de texto apelativo no título do tópico :´URGENTE!´[/list:u:0ff7aa71e2]
Peço que leia atentamente as [url=http://delphiforum.icft.com.br/forum/viewtopic.php?t=6689]Regras de Conduta[/url] para evitar que este fato se repita.
Se algum esclarecimento sobre o funcionamento do fórum ou sobre as Regras de Conduta for necessário, estou à sua disposição para ajudar-lhe. Se desejar, envie-me uma [url=http://delphiforum.icft.com.br/forum/privmsg.php?mode=post&u=2796]Mensagem Particular[/url].
Gostei + 0
13/10/2004
Fknyght
Tente verificar no seu algoritmo , se nenhuma variavel esta sendo estrapolada o limite dela
tipo
se voce estiver usando INT, passe para LONGINT,
se voce estiver usando uma matrix dinamina, verifique se não existe estrapolação dos indices da matrix, voce pode usar as funcoes LOW() e HIGH() para controlar uma matrix dinamica.
Por mais e so,
Espero ter ajudado.
Se ainda nao tiver resolvido, posta o codigo aqui pra gente dar uma olhadela
Gostei + 0
13/10/2004
Fórum Vini
acredito que o seu stack overflow está sendo causado porque a função está se chamando muitas vezes.. como os parâmetros são passados pela pilha, quando chega a um certo limite, a pilha chega no fim e estoura.. Não aconselho isso, mas você pode mudar o tamanho máximo da pilha, que iria apenas permitir que você use uma imagem maior, mas mesmo assim continuaria tendo um limite...
Outra solução(bem melhor) é implementar o algoritmo sem recursividade.. pela lógica, todo algoritmo recursivo pode ter seu correspondente sem recursividade, mas às vezes a solução não é tão evidente assim..
T+,
Vinicius;
Gostei + 0
13/10/2004
Gabriela
[b:e3591f495d]Undeclared Identifier[/b:e3591f495d], não é trabalho de faculdade não, se fosse seria mais facil, pq tiraria minhas duvidas com o professor.
[b:e3591f495d]Fknyght[/b:e3591f495d], assim que percebi o erro, a primeira coisa que verifiquei foi se não havia variavel sendo estrapolada, mas esta tudo dentro do limite normal. Depois eu coloco o código aqui, pois não estou com ele no momento.
[b:e3591f495d]Vini[/b:e3591f495d], concordo com vc, que o erro deve ser pelo fato da pilha estar ficando muito grande, mas não sabia que tem como alterar o tamanho da pilha. Como se pode fazer isso?
Estou pensando em realmente refazer o procedimento sem ser recursivo.
Gabriela.
Gostei + 0
13/10/2004
Fórum Vini
Com o seu projeto aberto vá em: Project > Project Options.. > Linker
Você deverá ver uma GroupBox com o título Memory Sizes, lá você controla o tamanho mínimo da pilha ( Min Stack Size ), máximo ( Max Stack Size ) e o Image base, que eu ainda não sei o que é mas vou procurar saber..
Procure fazer isso pois é a solução mais correta.
Espero ter ajudado,
Vinicius;
Gostei + 0
13/10/2004
Pehdepano
No seu caso, a única coisa que vc tem controle, e pode mudar, é a pilha criada para armazenar as coordenadas já percorridas. Por este motivo, o ideal, seria usar alocação dinâmica.
Porém, sua aplicação não me parece tão complexa a ponto de consumir tantos recursos e estourar a pilha do SO. É mais provável, que exista um erro de código que está fazendo chamadas recursisvas, gerando um [i:fd66cf7cc5]loop infinito[/i:fd66cf7cc5].
Para detalhes sobre alocação dinâmica, veja este site sobre[i:fd66cf7cc5] estruturas de dados[/i:fd66cf7cc5] [url]http://www.icmc.sc.usp.br/~sce182/[/url]
Gostei + 0
13/10/2004
Fórum Vini
Você está confundindo a pilha da aplicação com qualquer TStack que pode ser criada por aí...
O que acontece no caso dela é o seguinte:
Toda aplicação possui uma pilha, que ao contrário do que você disse, pode ser controlada pelo programa sim( instruções PUSH e POP do inline Assembler e o registrador EBP ), mas isso não vêm ao caso..
Quando uma função é chamada, os parâmetros são passados através da pilha( alguns por valor(Integer, Cardinal etc), outros com um ponteiro para o valor(Strings, Variants..) ) e esses valores só são liberados quando o método termina.. se o método é recursivo, ele vai se chamando, mas os parâmetros continuam na pilha.... se a função se chamar muitas vezes, a pilha chega ao fim e dá Stack Overflow..
Existem duas soluções, como eu já disse:
- Aumentar o tamanho da pilha, que eu não recomendo
- Não usar recursividade
Não é o caso de um loop infinito, mas realmente um método que se chama muitas, mas muitas vezes mesmo, pois como ela disse é chamado para cada pixel da imagem, numa imagem grande isso pode ocorrer...
Gostei + 0
13/10/2004
Pehdepano
Humm... Eu disse isso :?:
Se é recursivo, então só pode ser um método que chama a ele próprio várias vezes...
Quando digo Loop me refiro ao fato de o método chamar a si mesmo por várias vezes e não encontrar uma saída(Stack Overflow na pilha do SO, afinal de contas o SO é quem gerencia as chamadas recursivas).
Concordo plenamente.
Gostei + 0
13/10/2004
Fórum Vini
Veja só:
Se é a única coisa que tem controle, quer dizer que não existe outra...
Obviamente :lol:
Acontece que se houver espaço suficiente na pilha ele *vai* encontrar uma saída.. portanto não se trata de um loop *infinito*.
Desconheço o fato de haver uma pilha para o sistema operacional, a que eu sei que existe é a pilha da *aplicação*, que guarda os parâmetros passados pelas funções.. acho que você está confundindo isso.
Não é, quem gerencia a passagem de parâmetros para uma função é o próprio programa.. para chamadas recursivas não é diferente..
Gostei + 0
14/10/2004
Pehdepano
Gostei + 0
14/10/2004
Gabriela
Aumentei o tamanho da pilha, apenas para testar se realmente era esse o problema e funcionou. Refiz o procedimento sem recursividade e aparentemente esta tudo ok. :D
Gostei + 0
14/10/2004
Fórum Vini
Fico feliz por ter dado certo :D
Quando precisar, estamos aí :wink:
Gostei + 0
Clique aqui para fazer login e interagir na Comunidade :)