Проблема переполнения стека в рекурсивной программе на C - PullRequest
Новая
       8

Проблема переполнения стека в рекурсивной программе на C

1 голос
/ 28 марта 2010

Я получаю переполнение стека в одной из выполняемых мной рекурсивных функций ..

Вот код .. 

void* buddyMalloc(int req_size)
{ 
     // Do something here
     return buddy_findout(original_index,req_size); // This is the recursive call
}

void *buddy_findout(int current_index,int req_size)
{
    char *selected = NULL;

    if(front!=NULL)
    {
        if(current_index==original_index)
        {
            // Do something here
            return selected;
        }
        else
        {
            // Do Something here
            return buddy_findout(current_index+1,req_size);
        }
    }
    else
    {
        return buddy_findout(current_index-1,req_size);
    }
}

Считайте, что начальное значение индекса равно 4. Сначала он делает индекс-1, пока не достигнет индекса 0. а затем он возвращается к индексу 4 путем увеличения .. Это то, что я хочу реализовать. Но это дает переполнение стека с картой памяти в командной строке:

Вот вывод из моей оболочки: 

*** glibc detected *** ./473_mem: free(): invalid pointer: 0x00c274c0 ***
======= Backtrace: =========
/lib/tls/i686/cmov/libc.so.6[0xb50ff1]
/lib/tls/i686/cmov/libc.so.6[0xb526f2]
/lib/tls/i686/cmov/libc.so.6(cfree+0x6d)[0xb557cd]
./473_mem[0x8048b44]
./473_mem[0x8048b74]
./473_mem[0x8048b74]
./473_mem[0x8048944]
./473_mem[0x8048c87]
./473_mem[0x8048d31]
./473_mem[0x8048f79]
/lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xe6)[0xafcb56]
./473_mem[0x8048671]
======= Memory map: ========
0017c000-00198000 r-xp 00000000 08:01 5224       /lib/libgcc_s.so.1
00198000-00199000 r--p 0001b000 08:01 5224       /lib/libgcc_s.so.1
00199000-0019a000 rw-p 0001c000 08:01 5224       /lib/libgcc_s.so.1
00260000-00284000 r-xp 00000000 08:01 1927       /lib/tls/i686/cmov/libm-2.10.1.so
00284000-00285000 r--p 00023000 08:01 1927       /lib/tls/i686/cmov/libm-2.10.1.so
00285000-00286000 rw-p 00024000 08:01 1927       /lib/tls/i686/cmov/libm-2.10.1.so
006cd000-006e8000 r-xp 00000000 08:01 6662       /lib/ld-2.10.1.so
006e8000-006e9000 r--p 0001a000 08:01 6662       /lib/ld-2.10.1.so
006e9000-006ea000 rw-p 0001b000 08:01 6662       /lib/ld-2.10.1.so
00aa9000-00aaa000 r-xp 00000000 00:00 0          [vdso]
00ae6000-00c24000 r-xp 00000000 08:01 1900       /lib/tls/i686/cmov/libc-2.10.1.so
00c24000-00c25000 ---p 0013e000 08:01 1900       /lib/tls/i686/cmov/libc-2.10.1.so
00c25000-00c27000 r--p 0013e000 08:01 1900       /lib/tls/i686/cmov/libc-2.10.1.so
00c27000-00c28000 rw-p 00140000 08:01 1900       /lib/tls/i686/cmov/libc-2.10.1.so
00c28000-00c2b000 rw-p 00000000 00:00 0 
08048000-0804a000 r-xp 00000000 00:14 2176       /media/windows-share/OS/Project2/473_mem
0804a000-0804b000 r--p 00001000 00:14 2176       /media/windows-share/OS/Project2/473_mem
0804b000-0804c000 rw-p 00002000 00:14 2176       /media/windows-share/OS/Project2/473_mem
08483000-084a4000 rw-p 00000000 00:00 0          [heap]
b7600000-b7621000 rw-p 00000000 00:00 0 
b7621000-b7700000 ---p 00000000 00:00 0 
b7716000-b7819000 rw-p 00000000 00:00 0 
b7827000-b782a000 rw-p 00000000 00:00 0 
bfb96000-bfbab000 rw-p 00000000 00:00 0          [stack]
Aborted

Заранее спасибо ади

Ответы [ 2 ]

0 голосов
/ 28 марта 2010

Посмотрите на документацию по вашему компилятору, чтобы узнать, имеет ли он оптимизацию "хвостовой рекурсии". (Хотя теперь ваша проблема переполнения стека становится проблемой бесконечного цикла!) 

gcc -foptimize-sibling-calls ...
0 голосов
/ 28 марта 2010

Где установлен front?

В вызове: 

else 
    { 
        return buddy_findout(current_index-1,req_size); 
    } 
}

Когда front равен NULL, вы просто возвращаетесь к той же функции с меньшим current_index и продолжаете цикл и цикл. Нет условия остановки для current_index == 0

...