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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
colya
0 / 0 / 0
Регистрация: 04.02.2013
Сообщений: 12
#1

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

12.02.2013, 22:05. Просмотров 535. Ответов 3
Метки нет (Все метки)

Здравствуйте. У меня есть рекурсивная ф-ия, но глубина вызова довольно большая, в итоге стек переполняется и прога падает. Подскажите, как переписать ее в виде цикла и как вообще в дальнейшем действовать, если понадобиться переписывать ф-ию в цикл. У просто вообще никаких идей нет....

Вот сама ф-ия:
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;
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.02.2013, 22:05     Рекурсию в цикл
Посмотрите здесь:

Заменить рекурсию на цикл - C++
Как можно заменить данную рекурсию на цикл? #define pc putchar_unlocked void put (long long int num) { if (!num) { ...

заменить рекурсию на цикл - C++
Здравствуйте. У меня есть рекурсивная ф-ия, но глубина вызова довольно большая, в итоге стек переполняется и прога падает. Подскажите, как...

Как заменить цикл while на рекурсию? - C++
Как сделать в даной функции, вычисления через рекурсию, а не через цикл... тут происходит розложение в ряд Тейлора, ...

Найти значение формулы используя рекурсию и цикл - C++
Народ, помогите с задачей. Найти значение формулы используя рекурсию и цикл (2 способами: рекурсией и циклом).

Программа на рекурсию - C++
Задача о рюкзаке. В рюкзаке объёмом V содержится запас из N предметов. Для каждого предмета задан объем и стоимость. В рюкзак можно...

Задача на рекурсию - C++
Вот код проги которую я написал: #include &lt;iostream&gt; using namespace std; int factr(double i){ int answer; if(i==1) ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1928 / 1194 / 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
2225 / 1378 / 102
Регистрация: 05.06.2011
Сообщений: 3,799
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, на ++ лень расписывать.
Это функция Аккермана в рекурсивном и нерекурсивном варианте. Составляется что-то типа автомата или блок-схемы с метками и заводится свой стек. Разумеется, для понимабельность страдает
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.02.2013, 11:33     Рекурсию в цикл
Еще ссылки по теме:

Задача на рекурсию - C++
Помогите решить след. задачу: Вот мой вариант, но здесь не сохраняется порядок: void Func() { int x; cin&gt;&gt;x; if(0==x) ...

Задача на рекурсию - C++
Всем доброго времени суток. Прошу подсказать мне условие задачи на рекурсию(нам дали задание самим придумать себе задание и выполнить...

Задача на рекурсию - C++
помогите написать пожалуйста программу на с++ по теме рекурсия. Задано действительное A, найти среди чисел 1; 1+1/2; 1+1/2+1/3;.... ...

задача на рекурсию в си++ - C++
Даны числа a и b. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом.

Задача на рекурсию - C++
Дано натуральное число n. Выяснить, имеется ли среди чисел n, n+1, ..., 2n близнецы, т.е. простые числа, разность между которыми равна...

Задача на рекурсию - C++
Дано число. Вывести все цифры этого числа, не используя дополнительных библиотек, массивов, списков и т.д. Использовать только...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Евгений89
99 / 99 / 9
Регистрация: 17.04.2011
Сообщений: 554
Завершенные тесты: 2
15.02.2013, 11:33     Рекурсию в цикл #4
через while или do while
Yandex
Объявления
15.02.2013, 11:33     Рекурсию в цикл
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru