@Neponyatlivy

Объясните мне на пальцах рекурсию Фибоначчи F(4, например). Это самый простой алгоритм, а я не могу понять. Что мне делать?

Я не знаю, что мне делать. Я просто не могу понять суть работы! Все кроме меня усвоили алгоритм, но я просто не понимаю. Само число чисто в голове или на бумаге могу вычислить, но вот в коде этот процесс путает.
Вроде бы сначала всё понятно, F(4) постепенно опускается до одного, результаты в стаке ждут, он возвращает 1. А что дальше происходит - я просто не пойму. Сначала n=2, затем n=0, потом снова n=2, и в этот момент я полностью теряюсь в отладчике.
Может быть есть какая-то схема визуальная?
int Fib( int n)
{
     if (n == 0) return n;
     if (n == 1) return n;

     return  Fib(n - 1) + Fib(n - 2);
     
}

 Console.WriteLine(Fib(4));
  • Вопрос задан
  • 554 просмотра
Решения вопроса 4
AshBlade
@AshBlade Куратор тега C#
Просто хочу быть счастливым
Сначала n=2, затем n=0, потом снова n=2

Рекурсивные функции лучше визуализировать в виде дерева вызовов. В данном случае, это будет бинарное дерево, т.к. 1 функция (F(n)) может вызвать максимум 2 подфункции (F(n - 1) и F(n -2)).
Теперь самое интересное - представление в отладчике.
Вспомни, что функция заканчивается return F(n -1) + F(n - 2). Ответ на твой вопрос кроется здесь.
На самом деле эта конструкция разворачивается в нечто подобное:
int prev = F(n - 1);
int prevPrev = F(n - 2);
return prev + prevPrev;

На словах:
1. Ты вызываешь корневой F(2) - n = 2
2. Дебагер заходит в функцию и опускается до return F(n - 1) + F(n - 2)
3. Заходит в F(n - 1) - n = 1
4. Эта функция возвращает 1 - ты снова в родительской функции n = 2
5. Заходит в F(n - 2) - n = 0
6. Эта функция возвращает 1 - ты снова в родительской функции n = 2
7. Родительская (исходная) функция возвращает сумму - 1 + 1
Ответ написан
hint000
@hint000
у админа три руки
полностью теряюсь в отладчике
В отладчике неудобство, если шагать по одной строке за раз, а этот код написан так, что в одной строке сразу два рекурсивных вызова. Для наглядности отладки можно вместо одной строки return Fib(n - 1) + Fib(n - 2); сделать три строки:
int F1 = Fib(n - 1)
int F2 = Fib(n - 2);
return  F1 + F2;
Ответ написан
mindtester
@mindtester Куратор тега C#
http://iczin.su/hexagram_48
это функциональный стиль. может в том проблема? попробуйте тот же C#? Си? (без плюсов для начала).. любой диалект Pascal?
... это именно что бы понять.. а так, против питона ни че личного ))
разглядел теги... ща.. дабавлю..
изучите легкую модификацию алгоритма.. ну и проще с хранилищем, чем сразу с рекурсией.. просили же на пальцах? ;))
namespace ConsoleApp1
{
    public static class Fib
    {
        static List<int> fib = new List<int>();
        static int max = 15;
        public static void Main()
        {
            for (var i = 0; i < max; i++)
            {
                if (i == 0) fib.Add(0);
                else if (i == 1) fib.Add(1);
                else fib.Add(fib[i - 1] + fib[i - 2]);
                fib.print();
                "... next step...".print();
            }
        }
        public static void print(this string s) => Console.WriteLine(s);
        public static void print(this List<int> l) { foreach (var i in l) i.ToString().print(); }
    }
}
- функциональный стиль крут лаконичностью....
- слаб не предсказуемостью времени выполнения (а так же рисками переполнения стека..
- изучите что такое хвостовая рекурсия.. (после того как разберетесь с моей версией... ;)))... удачи
.. ну или так еще..
namespace ConsoleApp1
{
    public static class Fib
    {
        static List<int> fib = new List<int>();
        static int max = 15;
        public static void Main()
        {
            fib.Add(0);
            fib.Add(1);
            for (var i = 2; i < max; i++)
            {
                fib.Add(fib[i - 1] + fib[i - 2]);
                fib.print();
                "... next step...".print();
            }
        }
        public static void print(this string s) => Console.WriteLine(s);
        public static void print(this List<int> l) { foreach (var i in l) i.ToString().print(); }
    }
}
нарушения сна.. надо чем то заняться ))
.. и так, рекурсия мощный инструмент.. но особенно когда мы знаем некие принципы по кускам, а связать их нам трудно (привет Prolog ;)...
беру ваш исходный пример, и добавляю трассировку ;)
namespace ConsoleApp2
{
    public static class recursion
    {
        static long callcnt = 0;
        static int fib(int n)
        {
            $"_fib calling {++callcnt} count".print();

            var res = 0;

            if (n == 0 || n == 1) res = n;
            else res = fib(n - 1) + fib(n - 2);

            $"_fib return {res}".print();

            return res;
        }
        static int max = 15;
        public static void Main()
        {
            for (var i = 0; i < max; i++)
            {
                "... next fib...".print();
                fib(i).ToString().print();
            }
        }
        public static void print(this string s) => Console.WriteLine(s);
        public static void print(this List<int> l) { foreach (var i in l) i.ToString().print(); }
    }
}
.. реализуйте, и сравните как растет стоимость выполнения с ростом глубины погружения (номера числа Фибоначчи).. оптимизацию для одного вызова не применял.. так нагляднее )))
.. тем не менее, иногда рекурсия и красивый, и надежный способ решения запутанных задач )))
.. но, возможно, дорогой по времени и ресурсам )))

... еще подправил, подумал так нагляднее ;)))... программируйте, пробуйте все ))
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@vadimr
Вы хотите понять рекурсию, или как её обрабатывает процессор компьютера? Это разные вещи. В отладчике вы видите второе, фактически проекцию рекурсии на машинный язык, где рекурсия превращается в циклический алгоритм с использованием стека. На данном начальном этапе вы сами себя запутываете отладчиком.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы