Обьясните рекурсию на пальцах

Владимир848484

Привет всем! Классическая задача на рекурсию с факториалом. #include long int factorial(long int n) { if (n == 0 || n == 1) return 1; return n * factorial(n - 1); } Допустим n равно 7.Понятно что функция будет рекурсивно себя вызывать уменьшая за каждый вызов n на 1.Доходим до вызова с числом n равным 1. Выполняется условие на равенство 1 и функция возвращает 1 в main.В этом вызове мы не доходим до рекурсивного вызова.Так почему тогда происходит рекурсивный подьем после достижения n=1?Ведь после этого функция должна вернуть 1 и передать управление в функцию main cледующей команде после вызова функции factorial?
5 ответов

Владимир848484

функция должна вернуть 1 и передать управление в функцию main
Должна вернуть 1 не в main, а в то место, откуда она вызвана, т.е. в factorial(2), он вернет 2*1 в factorial(3) и т.д.


Владимир848484

Владимир848484, привет. Может-быть поможет: Рекурсивный метод. Принцип работа


Владимир848484

Доходим до вызова с числом n равным 1. Выполняется условие на равенство 1 и функция возвращает 1 в main.
Из main вызывается функция с числом 7. А функция с числом 1 вызывается из функции с числом 2, и в нее возвращает результат.


Владимир848484

После достижения n == 1 функция не сразу возвращается в main, а происходит возврат этой 1 в предыдущий шаг рекурсии, где в свою очередь происходит перемножение с текущим n и так до самого первого шага рекурсии и уже итоговый результат возвращается в main.


Владимир848484

Cпасибо! Теперь все как по полочкам)