Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Stack overflow - funkcja rekurencyjna

Ostatnio zmodyfikowano 2015-01-13 12:55
Autor Wiadomość
marani
Temat założony przez niniejszego użytkownika
Stack overflow - funkcja rekurencyjna
» 2015-01-12 16:05:33
Witam. Jestem w trakcie nauki programowania i jestem na etapie  takim, że mam problemy z zarządzaniem pamięcią, używaniem referencji, wyobrażeniem co jest bardziej optymalne itd.


Napisałam funckję rekurencyjną generującą wszystkie składniki, będące liczbami pierwszymi < 100, które dają pożądaną sumę np. 6:

1+2+3
1+5

itd.

C/C++
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;


vector < int > a( 26 ); // wygenerwoana w innej funkcji tablica 26 liczb pierwszych

vector < string > obliczSumy( vector < int > Liczby, vector < int > Indeksy, vector < string > Wyniki, int Pozadana_suma )
{
    bool Sprawdz;
    string wynik = "";
   
    int suma = 0;
    int n = Indeksy.size(); // 1
   
    for( int i = 0; i < Indeksy.size(); i++ )
         suma += Liczby[ Indeksy[ i ] ];
   
    if( suma < Pozadana_suma )
         Indeksy.push_back( Indeksy[ n - 1 ] );
   
   
    if( suma == Pozadana_suma )
    {
       
        for( int i = 0; i < Indeksy.size(); i++ )
        {
            ostringstream temp;
            temp << Liczby[ Indeksy[ i ] ];
            string str = temp.str();
           
            wynik += str;
           
            if( i != Indeksy.size() - 1 )
                 wynik += " + ";
           
        }
       
        Wyniki.push_back( wynik );
       
        cout << Wyniki[ Wyniki.size() - 1 ] << endl;
       
    }
   
   
    Indeksy[ Indeksy.size() - 1 ] += 1;
   
    Sprawdz = true;
   
    while( Sprawdz )
    {
        if( Indeksy[ Indeksy.size() - 1 ] <=( Liczby.size() - 1 ) ) //Liczby.size() - 1  = 4                               zmiana!!!
             Sprawdz = false;
        else
        {
            Indeksy.pop_back();
           
            if( Indeksy.size() != 0 )
                 Indeksy[ Indeksy.size() - 1 ] += 1;
            else
                 Sprawdz = false;
           
        }
    }
   
    if( Indeksy.size() > 0 )
         obliczSumy( Liczby, Indeksy, Wyniki, Pozadana_suma );
   
    return Wyniki;
   
   
}

int main()
{
   
    vector < int > robocza( 1 );
    robocza[ 0 ] = 0;
   
    vector < string > wyj;
   
    generowanieLiczbPierw();
   
    vector < string > WszystkieSumy;
   
    WszystkieSumy = obliczSumy( a, robocza, wyj, 22 );
   
    //for(int i=0; i<WszystkieSumy.size(); i++)
    // cout << "WszystkieSumy [ " << i << " ] = " << WszystkieSumy [0] << endl;
   
    system( "PAUSE" );
    return 0;
}

Przy ktoryms z kolei wywolaniu pojawia mi się komunikat w Visualu "Stack Overflow". Jak sobie z tym poradzić? Proszę o pomoc.
P-124729
killjoy
» 2015-01-12 16:15:00
Prawdopodobnie rekurencja zajmuje cały stos. Zmień tryb projektu na release.
P-124730
pekfos
» 2015-01-12 19:13:20
Zmień tryb projektu na release.
Haha, co to da..? Najlepiej w ogóle zastanowić się, po co tu jest ta rekurencja:
C/C++
vector < string > obliczSumy( vector < int > Liczby, vector < int > Indeksy, vector < string > Wyniki, int Pozadana_suma )
{
    // *nic rekurencyjnego*
   
    if( Indeksy.size() > 0 )
         obliczSumy( Liczby, Indeksy, Wyniki, Pozadana_suma );
   
    return Wyniki;
}
W skrócie: po nic. Tu powinna być pętla, a nie kosztowna rekurencja. Wstawienie tu do nie wymaga ani specjalnych zmian w kodzie, ani specjalnego myślenia. O ile w ogóle te wywołanie jest do czegoś potrzebne.
P-124753
killjoy
» 2015-01-12 19:30:15
Generalnie, może coś dać, ale nie musi. Zależy jak kompilator zoptymalizuje rekurencje ogonową. Chodzi o to, że w trybie release, może zostać zamieniona na wersję iteracyjną, więc nie powinien pojawić się overflow ( o co nota bene chodzi w temacie).
A to, że autor zrobił to w sposób rekurencyjny, to może być po prostu jego fanaberia, nic mi do tego (ja tylko dałem odpowiedź, która może pomóc przy podanych objawach, nie wnikałem głębiej w kod) :P
P-124755
marani
Temat założony przez niniejszego użytkownika
» 2015-01-13 12:55:58
Racja. While zmienił wszystko. Ubzdurałam sobie rekurencję, która była zbędna. Dziękuję :)
P-124794
« 1 »
  Strona 1 z 1