Форум программистов, компьютерный форум CyberForum.ru

Рекурсию в цикл - C++

Восстановить пароль Регистрация
 
colya
0 / 0 / 0
Регистрация: 04.02.2013
Сообщений: 12
12.02.2013, 22:05     Рекурсию в цикл #1
Здравствуйте. У меня есть рекурсивная ф-ия, но глубина вызова довольно большая, в итоге стек переполняется и прога падает. Подскажите, как переписать ее в виде цикла и как вообще в дальнейшем действовать, если понадобиться переписывать ф-ию в цикл. У просто вообще никаких идей нет....

Вот сама ф-ия:
C++
1
2
3
4
5
6
7
8
9
10
void f1 (int num)
{
arr [num] = 0;
 
for (vector <int>::iterator it = data [ num ].begin (); it < data [ num ].end (); it++)
    {
    if (arr [*it - 1]) f1 (*it - 1);
    arr [*it - 1] = 0;
    }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.02.2013, 13:06     Рекурсию в цикл #2
Судя по всему, это обход в глубину графа, представленного в виде списков смежности.
Набросал на коленке такое:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void f1 (int num)
{
   arr [num] = 0;
    
   for (unsigned i = 0; i < data [ num ].size(); i++)
   {
       const int next_vertex = data[num][i] - 1;
       
       if (arr [next_vertex])
       {
          arr [next_vertex] = 0;
          f1 (next_vertex);
       }
   }
}
 
void f2(int num)
{
   std::stack< std::pair<unsigned, unsigned> > stack;
   //pair.first - vertex number, pair.second - edge number
   
   stack.push( std::make_pair(num, 0) );
   
   arr[num] = 0;
   
   while (!stack.empty())
   {
      unsigned   vertex = stack.top().first;
      unsigned position = stack.top().second;
      stack.pop();
      
      if (position != data[num].size() - 1u)
      {
         stack.push( std::make_pair(vertex, position + 1) ); //next iteration
      }
      
      const unsigned next_vertex = data[num][position] - 1;
      
      if (arr[next_vertex])
      {
         arr[next_vertex] = 0;
         stack.push( std::make_pair(next_vertex, 0) );
      }
   }
}
Не факт, что код работает(я его вообще не тестировал), но общая идея должна быть понятна.
iifat
2179 / 1332 / 96
Регистрация: 05.06.2011
Сообщений: 3,692
15.02.2013, 09:37     Рекурсию в цикл #3
Ну, делается это примерно вот так:
Perl 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
proc accrec {m n} {
  puts "$m $n"
  if {!$m} {
    expr {$n+1}
  } elseif {!$n} {
    accrec [expr {$m-1}] 1
  } else {
    accrec [expr {$m-1}] [accrec $m [expr {$n-1}]]
  }
}
 
puts [accrec 3 3]
 
proc accloop {m n} {
  set state 1
  set stack {}
  set acc 0
  set mm $m; set nn $n
  while {1} {
    puts ":: $state $mm $nn"
    set action 0
    switch $state {
      {1} {
    if {!$mm} {set acc [expr {$nn+1}]; set action -1} else {set state 2}
      }
      {2} {
    if {!$nn} {set newmm [expr {$mm-1}]; set newnn 1; set action 1; set state 3} else {set state 4}
      }
      {3} {
    set action -1
      }
      {4} {
    set newmm $mm; set newnn [expr {$nn-1}]; set action 1; set state 5
      }
      {5} {
    set newmm [expr {$mm-1}]; set newnn $acc; set action 1; set state 6
      }
      {6} {
    set action -1
      }
    }
    if {$action==-1} { # возврат
      if {![llength $stack]} break
      set stack [lassign $stack mm nn state]
      puts "<== ($mm $nn $state) $stack -- $acc"
    }
    if {$action==1} { # рекурсия
      set stack [linsert $stack 0 $mm $nn $state]
      puts "==> $stack"
      set state 1; set mm $newmm; set nn $newnn
    }
  }
  return $acc
}
 
puts [accloop 3 3]
Это tcl, на ++ лень расписывать.
Это функция Аккермана в рекурсивном и нерекурсивном варианте. Составляется что-то типа автомата или блок-схемы с метками и заводится свой стек. Разумеется, для понимабельность страдает
Евгений89
 Аватар для Евгений89
99 / 99 / 9
Регистрация: 17.04.2011
Сообщений: 554
Завершенные тесты: 2
15.02.2013, 11:33     Рекурсию в цикл #4
через while или do while
Yandex
Объявления
15.02.2013, 11:33     Рекурсию в цикл
Ответ Создать тему
Опции темы

Текущее время: 02:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru