斐波那契数列在C#中的递归解法有哪些

在C#中，实现斐波那契数列的递归解法主要有两种方法：递归函数和记忆化递归

1. 递归函数：

using System;

class Program
{
    static void Main(string[] args)
    {
        int n = 10; // 输入需要计算的斐波那契数列项数
        Console.WriteLine($"Fibonacci({n}) = {Fibonacci(n)}");
    }

    static int Fibonacci(int n)
    {
        if (n <= 1)
            return n;
        else
            return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

这种方法的缺点是效率较低，因为存在大量重复计算。

1. 记忆化递归：

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int n = 10; // 输入需要计算的斐波那契数列项数
        Dictionary<int, int> memo = new Dictionary<int, int>();
        Console.WriteLine($"Fibonacci({n}) = {Fibonacci(n, memo)}");
    }

    static int Fibonacci(int n, Dictionary<int, int> memo)
    {
        if (n <= 1)
            return n;

        if (!memo.ContainsKey(n))
        {
            memo[n] = Fibonacci(n - 1, memo) + Fibonacci(n - 2, memo);
        }

        return memo[n];
    }
}

这种方法通过使用字典（Dictionary）存储已经计算过的斐波那契数列项，从而避免了重复计算，提高了效率。

版权声明

本文内容由互联网用户自发贡献，该文观点仅代表作者本人
本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。