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

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

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

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

12.02.2013, 22:05. Просмотров 555. Ответов 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;
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.02.2013, 22:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсию в цикл (C++):

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

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

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

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

Почему цикл на при 1 уходит в бесконечный цикл? - C++
#define _CRT_SECURE_NO_WARNINGS #include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;string.h&gt; int main() { int x=0, y=0,...

Цикл: цикл for вообще никак не воспринимается транслятором - C++
Пишу программу, которая производит различные действия с одномерным массивом. Возникла следующая проблема: цикл for вообще никак не...

3
diagon
Higher
1929 / 1195 / 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) );
      }
   }
}
Не факт, что код работает(я его вообще не тестировал), но общая идея должна быть понятна.
0
iifat
2252 / 1408 / 105
Регистрация: 05.06.2011
Сообщений: 3,864
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, на ++ лень расписывать.
Это функция Аккермана в рекурсивном и нерекурсивном варианте. Составляется что-то типа автомата или блок-схемы с метками и заводится свой стек. Разумеется, для понимабельность страдает
0
Евгений89
99 / 99 / 9
Регистрация: 17.04.2011
Сообщений: 554
Завершенные тесты: 2
15.02.2013, 11:33 #4
через while или do while
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.02.2013, 11:33
Привет! Вот еще темы с ответами:

Цикл for/Цикл while Помогите срочно пожалуйста... - C++
1.Вычислить и вывести на экран в виде таблицы значения функции F от x1 до x2 с шагом dx. где a, b и c - действительные числа. 2.Цикл...

Задание на цикл с параметром и цикл с постусловием - C++
Помогите пожалуйста написать программу с этими циклами. 1. Вычислить и напечатать таблицу значений функции Z= (e^-x)sinx для 0&lt;=x&lt;=П,...

Задача на рекурсию - C++
Нашел одну задачу, она по моему на рекурсию, но не могу реализовать это. Сколько существует чисел от 1 до n, таких, что цифры числа...

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


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

Или воспользуйтесь поиском по форуму:
4
Yandex
Объявления
15.02.2013, 11:33
Ответ Создать тему
Опции темы

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