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

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

Войти
Регистрация
Восстановить пароль
 
fuzzytoozy
8 / 8 / 1
Регистрация: 23.11.2012
Сообщений: 94
#1

Рекурсия - C++

19.10.2013, 14:49. Просмотров 512. Ответов 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);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.10.2013, 14:49     Рекурсия
Посмотрите здесь:

Рекурсия C++
Рекурсия C++
Рекурсия=( C++
C++ Рекурсия
Рекурсия C++
Рекурсия C++
рекурсия C++
рекурсия C++
C++ Рекурсия
C++ Рекурсия
C++ рекурсия
C++ Рекурсия

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dzrkot
zzzZZZ...
518 / 348 / 53
Регистрация: 11.09.2013
Сообщений: 1,995
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
fuzzytoozy
8 / 8 / 1
Регистрация: 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 переменная. Как они обе поменяли значение!?!?!
dzrkot
zzzZZZ...
518 / 348 / 53
Регистрация: 11.09.2013
Сообщений: 1,995
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

я не понимаю что непонятно...)
zss
Модератор
Эксперт С++
6244 / 5847 / 1891
Регистрация: 18.12.2011
Сообщений: 14,980
Завершенные тесты: 1
19.10.2013, 21:04     Рекурсия #5
Легче будет понять в отладчике.
Поставьте останов на строку 32.
И далее выполняйте код построчно с заходом в функции
(в VS - клавиша F11). При этом следите за переменной mid.
fuzzytoozy
8 / 8 / 1
Регистрация: 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
Yandex
Объявления
19.10.2013, 21:32     Рекурсия
Ответ Создать тему
Опции темы

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