Problema com recursividade (Stack OverFlow)
Tenho um algoritmo recursivo, parecido com o problema do labirinto.
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
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
Curtidas 0
Respostas
Rômulo Barros
13/10/2004
:arrow: [b:0a0efdb594][color=blue:0a0efdb594]Isso tá ´cheirando´ trabalho de faculdade !!![/color:0a0efdb594] [/b:0a0efdb594] :lol: :lol: :lol: :lol:
GOSTEI 0
Vinicius2k
13/10/2004
[b:0ff7aa71e2][color=red:0ff7aa71e2]Notificação de Infração às Regras de Conduta :[/color:0ff7aa71e2][/b:0ff7aa71e2]
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].
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
Fknyght
13/10/2004
[b:1124382800]Stack Overflow[/b:1124382800] é estouro da pilha, memoria , etc
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
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
Fórum Vini
13/10/2004
Olá,
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;
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
Gabriela
13/10/2004
[b:e3591f495d]Vinicius[/b:e3591f495d], me desculpe por infringir as regras do forum, não foi minha intenção.
[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.
[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
Fórum Vini
13/10/2004
não sabia que tem como alterar o tamanho da pilha. Como se pode fazer isso?
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..
Estou pensando em realmente refazer o procedimento sem ser recursivo.
Procure fazer isso pois é a solução mais correta.
Espero ter ajudado,
Vinicius;
GOSTEI 0
Pehdepano
13/10/2004
[i:fd66cf7cc5]Recursividade é recomendada para facilitar a escrita do código. Em muitos casos, porém, ela não é a melhor solução pois consome muitos recursos, já que todos os processos são empilhados pelo ´sistema operacional´.[/i:fd66cf7cc5]
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]
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
Fórum Vini
13/10/2004
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.
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
É mais provável, que exista um erro de código que está fazendo chamadas recursisvas, gerando um [i:716f2f3186]loop infinito[/i:716f2f3186].
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
Pehdepano
13/10/2004
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..
Humm... Eu disse isso :?:
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...
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).
- Não usar recursividade
Concordo plenamente.
GOSTEI 0
Fórum Vini
13/10/2004
Humm... Eu disse isso :?:
Veja só:
No seu caso, [b:3f75bacd77]a única coisa que vc tem controle, e pode mudar[/b:3f75bacd77], é a pilha criada para armazenar as coordenadas já percorridas
Se é a única coisa que tem controle, quer dizer que não existe outra...
Se é recursivo, então só pode ser um método que chama a ele próprio várias vezes...
Obviamente :lol:
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
Acontece que se houver espaço suficiente na pilha ele *vai* encontrar uma saída.. portanto não se trata de um loop *infinito*.
(Stack Overflow na pilha do SO
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.
afinal de contas o SO é quem gerencia as chamadas recursivas.
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
Pehdepano
13/10/2004
:arrow: :?
GOSTEI 0
Gabriela
13/10/2004
Vini, valeu pela ajuda!
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
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
Fórum Vini
13/10/2004
Vini, valeu pela ajuda!
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
Fico feliz por ter dado certo :D
Quando precisar, estamos aí :wink:
GOSTEI 0