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

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

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

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

22.09.2012, 20:54. Просмотров 1204. Ответов 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 строчка будет сперва и по каких правилах будет вызывать, понятно что сверху в низ, но как оно работает не понятно)

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

объсните принцип работы C++
C++ Принцип реализации и работы со стеком
Принцип работы конструктора C++
Принцип работы switch C++
C++ Принцип работы программы
C++ Принцип работы функции
Принцип работы strpbrk C++
C++ Объясните принцип работы программы
Объясните принцип работы программы C++
Принцип работы fstream C++
Принцип работы pthread_join C++
C++ Getline принцип работы

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Форумчанин
Эксперт С++
 Аватар для Kastaneda
4253 / 2785 / 219
Регистрация: 12.12.2009
Сообщений: 7,109
Записей в блоге: 1
Завершенные тесты: 1
22.09.2012, 20:56     Принцип работы рекурсии #2
Цитата Сообщение от botasa Посмотреть сообщение
но сам ПРИНЦИП работы рекурсии ПРОГРАММНО не увидел
Вот тут я когда то давно попытался объяснить. Написано не очень грамотно, но вроде понятно
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 такт
I.M.
 Аватар для I.M.
564 / 547 / 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) заканчивает работать
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1242 / 991 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
23.09.2012, 00:33     Принцип работы рекурсии #5
Насколько же с моделью подстановки всё проще объясняется...
Yandex
Объявления
23.09.2012, 00:33     Принцип работы рекурсии
Ответ Создать тему
Опции темы

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