Лабораторная работа по C#. Рекурсия. Числа Фибоначчи

Задача: 1) составьте программу для вычисления и вывода n-го числа Фибоначчи с использованием рекурсии; 2) составьте программу для вычисления и вывода n-го числа Фибоначчи с использованием рекурсии; 3) рассчитайте время, затрачиваемое каждым из методов расчёта на получение числа Фибоначчи.

Решение лабораторной работы

Рекурсивный метод расчёта чисел Фибоначчи

Числа Фибоначчи  — элементы числовой последовательности в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел, т.е. последовательность следующая 0, 1, 1, 2, 3, 5, 8..... Общая формула для расчёта n-го члена последовательности выглядит следующим образом: F(0) = 0; F(1) = 1, F(n) = F(n-1)+F(n-2). В принципе, уже, исходя из представленной формулы мы можем составить рекурсивный метод в котором условием выхода из рекурсии (базовым сценарием) будет условие:

if ((n == 0) || (n == 1))
    return n;

Сам рекурсивный метод для расчёта числа Фибоначчи будет выглядеть следующим образом:

static long Fib(int n)
{
    if ((n == 0) || (n == 1))
        return n;
    return Fib(n - 1) + Fib(n - 2);
}

Исходный код программы:

namespace ConsoleApp1
{
    internal class Program
    {
        static long Fib(int n)
        {
            if ((n == 0) || (n == 1))
                return n;
            return Fib(n - 1) + Fib(n - 2);
        }

        static void Main(string[] args)
        {
            Console.WriteLine(Fib(0));
            Console.WriteLine(Fib(1));
            Console.WriteLine(Fib(2));
            Console.WriteLine(Fib(3));
            Console.WriteLine(Fib(4));
            Console.WriteLine(Fib(5));
        }
    }
}

Проверим работу программы. В результате мы должны получить последовательность: 0, 1, 1, 2, 3, 5. Результат:

Верный результат получен. Переходим ко второй части задания.

Метод расчёта чисел Фибоначчи без использования рекурсии

Этот метод будет немного тяжелее в плане прочтения, но, тем не менее, тоже относительно простой. Для расчёта используем цикл for:

static long Fib2(int n)
{
    if (n == 0) return 0;

    int prev = 0;
    int next = 1;
    for (int i = 1; i < n; i++)
    {
        int sum = prev + next;
        prev = next;
        next = sum;
    }
    return next;
}

Проверим результат расчёта, например, 10-го числа с использованием этого метода и рекурсивного:

static void Main(string[] args)
{
    Console.WriteLine($"Результат рекурсивного метода: {Fib(10)}");
    Console.WriteLine($"Результат метода с циклом: {Fib2(10)}");
}

Вывод в консоли

Расчет времени, затрачиваемого каждым из методов расчёта на получение числа Фибоначчи

Для расчёта времени, затрачиваемого на выполнение метода воспользуемся классом Stopwatch, который располагается в пространстве имен System.Diagnostics. Подключаем это пространство имен в свой проект:

using System.Diagnostics;

Дописываем код метода Main следующим образом:

static void Main(string[] args)
{
    Stopwatch sw = Stopwatch.StartNew(); //запускаем таймер
    long result = Fib(40); //рассчитываем 40-е число 
    sw.Stop(); //останавливаем таймер
    Console.WriteLine($"Результат рекурсивного метода: {result}. Время выполнения операции {sw.ElapsedTicks} тактов");

    sw.Restart(); //перезапускаем таймер
    result = Fib2(40); //рассчитываем 40-е  число
    sw.Stop(); //останавливаем таймер
    Console.WriteLine($"Результат метода с циклом: {result}. Время выполнения операции {sw.ElapsedTicks} тактов");
}

Результат выполнения:

Итого

В этой лабораторной работе мы закрепили свои знания о работе рекурсивных методов в C#, а также наглядно продемонстрировали различия в скорости работы рекурсивных методов и методов, не использующих рекурсию.