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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
botasa
3 / 3 / 0
Регистрация: 18.01.2011
Сообщений: 131
#1

Принцип работы рекурсии - C++

22.09.2012, 20:54. Просмотров 1362. Ответов 4
Метки нет (Все метки)

Искал в инете и в поиске, но никак не могу понять принцип работы рекурсии программно.
Допустим есть функция
C++
1
2
3
4
int f(int n) {
   if(0 == n) return 0;
   else return n % 10 + f(n / 10);
}
если переделать данную функцию
C++
1
2
3
4
5
6
7
static int i;
int f(int n) {
   i = n;
   cout << i << endl;
   if(0 == n) return 0;
   else return n % 10 + f(n / 10);
}
и вызвать ее f(100500);

то результат в консоли будет
100500
10050
1005
100
10
1
0
6 - конечный результат в точке вызова. То есть данная рекурсивная функция подсчитает суму цифр в числе. НО как именно оно работает я не понимаю при передачи xxx + f(n / 10) тут понятно, почему дальше будет вот такой результат :
100500
10050
1005
100
10
1

НО тут не понятно как работает n % 10 в этой функции и куда оно это все присваивает, что в конце будет цифра 6. И тоже самое в Фибоначчи return f(n - 1) + f(n - 2). Тут не понятно, что сперва вызовет f(n - 1) или f(n - 2), наверно на 2 части разобьется, как ТРЕУГОЛЬНИК в инете видел, но КАК оно потом это все в кучку слепит и в конце даст один результат, то же самое и из ФАКТОРИАЛОМ n * f(n - 1), f(n - 1) - это будет постоянно вызывать а когда и как оно будет на n эти вызовы перемножать ????

То что оно постоянно уходит в глубину и ест много ресурсов понятно, и когда достигнет определенного момента проверки, при которой даст FALSE тоже понятно, но как оно вернет назад результат умножит и другие действия сделается не понятно !!! Вот например в рекурсивный способ решения задачи на сортировку СЛИЯНИЯМ там вроде 2 рекурсии потом и тоже самое в ХАНОЙСКИХ башнях (в башнях вопше не понятно 1 или 2 или 3 строчка будет сперва и по каких правилах будет вызывать, понятно что сверху в низ, но как оно работает не понятно)

В инете нашел много теории и всякие мат. и другие задачи, но сам ПРИНЦИП работы рекурсии ПРОГРАММНО не увидел
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.09.2012, 20:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Принцип работы рекурсии (C++):

Принцип работы switch - C++
Всем доброго времени суток. Изучаю самостоятельно С++. Возник вопрос по поводу функции switch. Каким образом она работает на данном...

Getline принцип работы - C++
Не совсем понимаю как влияет цикл. Да, выводится все сообщение, каждая срока с новой строки. Но, как тут происходит взаимодействие с...

Принцип работы fstream - C++
Допустим у нас есть файл из четырех чисел, например: 453 32 43 54. Я создаю экземпляр класса ifstream и инициализирую массив из четырех...

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

Принцип работы pthread_join - C++
Есть код функции pthread_join из glibc. Подскажите: 1) Номер строки и что происходит, если для потока уже вызвали pthread_join? Тут...

Принцип работы strpbrk - C++
Изначально я думал, что он возвращает только 1ый символ, но эта функция _string operator*(_string &amp;a){ _string t; ...

4
Kastaneda
Нарушитель
Эксперт С++
4669 / 2873 / 232
Регистрация: 12.12.2009
Сообщений: 7,307
Записей в блоге: 2
Завершенные тесты: 1
22.09.2012, 20:56 #2
Цитата Сообщение от botasa Посмотреть сообщение
но сам ПРИНЦИП работы рекурсии ПРОГРАММНО не увидел
Вот тут я когда то давно попытался объяснить. Написано не очень грамотно, но вроде понятно
0
botasa
3 / 3 / 0
Регистрация: 18.01.2011
Сообщений: 131
22.09.2012, 23:54  [ТС] #3
спасибо, пошел читать, если что я сюда отпишу !

Добавлено через 2 часа 38 минут
Почитал я ваши посты, но так и не в курил.

я вот пробую разобраться на самом простом :

int f(int i)
{
if(i <= 1) return 1;
else return i * f(i - 1);
}
f(3);
то
i = 3;
i = 2;
i = 1;
и обратно.
но я так понимаю что при запуску i = 3, тогда потом f(i - 1), тогда i = 2 и т.д. потом обратно и начиная из с 1, оно начинает множить 1, потом на 2, потом на 3 и финал или как ??? или как то по другом ??? ну такой результат сверху мне показал debuger в

Добавлено через 2 минуты
Почитал я ваши посты, но так и не в курил.

я вот пробую разобраться на самом простом :

int f(int i)
{
if(i <= 1) return 1;
else return i * f(i - 1);
}
f(3);
то
i = 3;
i = 2;
i = 1;
и обратно.
но я так понимаю что при запуску i = 3, тогда потом f(i - 1), тогда i = 2 и т.д. потом обратно и начиная из с 1, оно начинает множить 1, потом на 2, потом на 3 и финал или как ??? или как то по другом ??? ну такой результат сверху мне показал debuger в IDE. Но если сделать 10 + i + f(i - 1) при f(3), тогда результат будет 46, то есть ЧИСЛО 10 будет 4 раза вызываться, а сама рекурсия показывает 3 вызова ...

Добавлено через 3 минуты
но если 10 * i + f(i - 1) при f(3) результат будет 600, уже 3 итерации ... при умножении и при додавание оно отличатся в 1 такт
0
I.M.
565 / 548 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
23.09.2012, 00:10 #4
C++
1
2
3
4
5
int f(int i)
{
   if(i <= 1)return 1;
   return i+f(i-1);
}
Теперь вызываем f(3)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int f(3)
{
   if(3 <= 1)return 1;//false
   return 3+f(2);//вызывается f(2), а f(3) ждет, когда она доработает. Т.е. f(3) будет висеть в памяти
   //когда f(2) вернет результат, то к нему добавится 3. f(3) вернет эту сумму и закончит работать
}
 
int f(2)
{
   if(2 <= 1)return 1;//false
   return 2+f(1);//вызывается f(1), а f(2) ждет, когда она доработает. Т.е. f(2) будет висеть в памяти
   //когда f(1) вернет результат, то к нему добавится 2. f(2) вернет эту сумму и закончит работать
 
}
 
int f(1)
{
   if(1 <= 1)return 1;//true - выход из рекурсии
   return 2+f(0);//уже не выполнится
 
}
Таким образом, последовательность такая:
f(3) начинает работать
f(2) начинает работать
f(1) начинает работать
f(1) заканчивает работать
f(2) заканчивает работать
f(3) заканчивает работать
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
23.09.2012, 00:33 #5
Насколько же с моделью подстановки всё проще объясняется...
0
23.09.2012, 00:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.09.2012, 00:33
Привет! Вот еще темы с ответами:

Принцип работы программы - C++
Смысл программы: подсчет количества слов и предложений из подключенного файла. Код есть, только не понимаю, почему подсчет слов (s) идет...

Принцип работы конструктора - C++
Объясните пожалуйста на простом примере принцип работы конструктора в С++. Я сейчас начал их изучать и никак не могу въехать. Спасибо.

объсните принцип работы - C++
Объясните кому не сложно принцип работы данной программы Планируется переписывание на паскале #include &lt;fstream&gt; using namespace ...

Принцип реализации и работы со стеком - C++
Здравствуйте! В ходе изучения применения стека на c++, начал рассматривать нижеприведенный пример (Программа вычисляет обратную польскую...


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

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

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