Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
fuzzytoozy
9 / 9 / 7
Регистрация: 23.11.2012
Сообщений: 94
#1

Рекурсия

19.10.2013, 14:49. Просмотров 629. Ответов 5
Метки нет (Все метки)

Есть такой код. В нем рисуется что то вроде линейки. Данный код предназначен для иллюстрации работы рекурсии. Может мне кто нибудь объяснить. Вот при первом вызове subdivide палочка ставится посередине, значение середины 32. Далее палочки ставятся на 32, 16 и 48, ок. Но что происходит потом я не могу понять. Происходит вызов subdivide с level 3, она ставит палочку на 32 и вызывает subdivide с level 2, которая, в свою очередь ставит палочку на 16 и вызывает subdivide с level 1, которая ставит палочку на значении 8. Но как в этом рекурсивном цикле палочка оказывается на значении 24 я не понимаю. Откуда она его берёт!?!? Объясните пожалуйста, всю голову сломал уже....

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
// ruler.cpp -- using recursion to subdivide a ruler
#include <iostream>
const int Len = 66;
const int Divs = 6;
void subdivide(char ar[], int low, int high, int level);
int main()
{
    char ruler[Len];
    int i;
    for (i = 1; i < Len - 2; i++)
        ruler[i] = ' ';
    ruler[Len - 1] = '\0';
    int max = Len - 2;
    int min = 0;
    ruler[min] = ruler[max] = '|';
    std::cout << ruler << std::endl;
    for (i = 1; i <= Divs; i++)
    {
        subdivide(ruler,min,max, i);
        std::cout << ruler << std::endl;
        for (int j = 1; j < Len - 2; j++)
            ruler[j] = ' ';  // reset to blank ruler
    }
    // std::cin.get();
    std::system("PAUSE");
    return 0;
}
 
void subdivide(char ar[], int low, int high, int level)
{
    if (level == 0)
        return;
    int mid = (high + low) / 2;
    ar[mid] = '|';
    std::cout << "Recursion at level: " << level << std::endl
    << "Mid = " << mid << std::endl;
    subdivide(ar, low, mid, level - 1);
    subdivide(ar, mid, high, level - 1);
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.10.2013, 14:49
Ответы с готовыми решениями:

Рекурсия
Помогите написать функцию которая будет считать эту рекуррентную формулу с...

Рекурсия
Как переделать программу в рекурсию? char S='S', T='T', M={NULL}; int...

Рекурсия
Разработать рекурсивную функцию не возврашающую значений: Дано натуральное...

РЕкурсия
Мне нужно 5 задач по рекурсии с решениями,)))есмли не сложно-помогите, может...

Рекурсия
#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;time.h&gt; #include &lt;iostream&gt;...

5
dzrkot
zzzZZZ...
523 / 354 / 94
Регистрация: 11.09.2013
Сообщений: 2,039
19.10.2013, 16:50 #2
знакомая програмка из Стивена Прата))

C++
1
2
3
 
subdivide(ar, low, mid, level - 1);
subdivide(ar, mid, high, level - 1)
обрати внимание функция 1ый раз вызывается для low mid, 2ой, для mid high

low=0, high = LEN-2=64,
1) mid = 0 + 64 / 2 = 32
2) mid+high=32+64=96
mid=96/2=48
0
fuzzytoozy
9 / 9 / 7
Регистрация: 23.11.2012
Сообщений: 94
19.10.2013, 18:53  [ТС] #3
Да, из него родимого. Нет, это я понял. Меня интересует именно то, каким образом функция получает значение 24 в переменную mid. Потому что это значение должно получаться именно при вызове первой функции с mid в качестве high.
Ну вот например: level = 3, значит при вызове первой функции level-1 = 2. Получаем что mid = 16 так? то бишь 32/2. Потом вызывается эта же функция с level -1, level = 1. Получается mid = 16/2 = 8, так?. Далее функция опять вызовет сама себя но натолкнется на проверку условия level == 0 и выполнит оператор return. Что происходит дальше? откуда программа берет значение 24 в переменную mid?

Добавлено через 1 час 35 минут
в общем я вставлял в код принтф и заметил такую штуку. В определенный момент, при вызове функции, значение low в ней становится 16 а high = 32, они складываются, делятся на 2 и получается 24. НО КАК!?!? Ведь при вызове функции один параметр high или low всегда константый.... либо low = 0 и high переменная, либо high = 64 а low переменная. Как они обе поменяли значение!?!?!
0
dzrkot
zzzZZZ...
523 / 354 / 94
Регистрация: 11.09.2013
Сообщений: 2,039
19.10.2013, 20:39 #4
Цитата Сообщение от fuzzytoozy Посмотреть сообщение
Да, из него родимого. Нет, это я понял. Меня интересует именно то, каким образом функция получает значение 24 в переменную mid. Потому что это значение должно получаться именно при вызове первой функции с mid в качестве high.
Ну вот например: level = 3, значит при вызове первой функции level-1 = 2. Получаем что mid = 16 так? то бишь 32/2. Потом вызывается эта же функция с level -1, level = 1. Получается mid = 16/2 = 8, так?. Далее функция опять вызовет сама себя но натолкнется на проверку условия level == 0 и выполнит оператор return. Что происходит дальше? откуда программа берет значение 24 в переменную mid?

Добавлено через 1 час 35 минут
в общем я вставлял в код принтф и заметил такую штуку. В определенный момент, при вызове функции, значение low в ней становится 16 а high = 32, они складываются, делятся на 2 и получается 24. НО КАК!?!? Ведь при вызове функции один параметр high или low всегда константый.... либо low = 0 и high переменная, либо high = 64 а low переменная. Как они обе поменяли значение!?!?!
долго пытался понять то, что тебе не понять...

low и high не меняются, меняется только mid. Мы при вызове функции, просто от середины меняем границы функции, в одном случае вместо low ставим mid, в другом вместо high. Ты функцию вызываешь первый раз, subdivide(ar, low(0), high(64), level - 1);
потом она вызывает сама себя с разными значениями:
subdivide(ar, low(0), mid(32), level - 1);
subdivide(ar, mid(32), high(64), level - 1);
дальше mid снова меняется, и для каждой функции из этих 2ух он будет свой, т.е. в 1ом случае (0+32)/2=16, в другом (32+64)/2=48, потом каждая из функций вызывает другие две себя, дргумими значениями mid

я не понимаю что непонятно...)
0
zss
Модератор
Эксперт С++
7097 / 6628 / 4196
Регистрация: 18.12.2011
Сообщений: 17,474
Завершенные тесты: 1
19.10.2013, 21:04 #5
Легче будет понять в отладчике.
Поставьте останов на строку 32.
И далее выполняйте код построчно с заходом в функции
(в VS - клавиша F11). При этом следите за переменной mid.
0
fuzzytoozy
9 / 9 / 7
Регистрация: 23.11.2012
Сообщений: 94
19.10.2013, 21:32  [ТС] #6
Цитата Сообщение от dzrkot Посмотреть сообщение
долго пытался понять то, что тебе не понять...

low и high не меняются, меняется только mid. Мы при вызове функции, просто от середины меняем границы функции, в одном случае вместо low ставим mid, в другом вместо high. Ты функцию вызываешь первый раз, subdivide(ar, low(0), high(64), level - 1);
потом она вызывает сама себя с разными значениями:
subdivide(ar, low(0), mid(32), level - 1);
subdivide(ar, mid(32), high(64), level - 1);
дальше mid снова меняется, и для каждой функции из этих 2ух он будет свой, т.е. в 1ом случае (0+32)/2=16, в другом (32+64)/2=48, потом каждая из функций вызывает другие две себя, дргумими значениями mid

я не понимаю что непонятно...)
Ты просто не понимаешь что я спрашиваю. Я понимаю что меняется значение только mid и оно передается как high или low. Суть вопроса не в том КАК это происходит. А каким образом получается число 24 в mid. Ты проследи цикл и попробуй мне объясни это. там получается так что в функции которой ПЕРЕДАЛИ MID в качестве параметра low = 16, а high = 32. Я и спрашиваю каким образом получаются такие значения, если у первого вызова функции low всегда = 0 и в качества параметра high передается mid, а у второго high всегда = 64 и в качестве параметра low. Тогда получается что одновременно могут изменяться только либо high либо low в одной функции, другое значение всегда остается постоянным 0 или 64, тогда каким образом они приняли вид 16 и 32....я не понимаю

Добавлено через 11 минут
Цитата Сообщение от zss Посмотреть сообщение
Легче будет понять в отладчике.
Поставьте останов на строку 32.
И далее выполняйте код построчно с заходом в функции
(в VS - клавиша F11). При этом следите за переменной mid.
я знаю в каком месте она меняется таким образом, я просто не понимаю почему и как именно таким образом. Откуда берется значение 24
0
19.10.2013, 21:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.10.2013, 21:32

Рекурсия
на картинке файлик из википедии в которой говорится что рекусия имеет вид...

рекурсия B c++
пожалуйста помогите,почему не работает? дело в рекурсии,функция func1...

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


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

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