DreamMX Weblogs

查看本文的中文版，请点击这里。

Last article illustrated how to use the recursion to achieve factorial calculation by a simple example, and this article will show another classic application of recursion – Fibonacci numbers.

Fibonacci numbers refers to such an infinite numbers: 1, 1, 2, 3, 5, 8, etc. Except the first two numbers, each number is the sum of the two preceding numbers.

Since the Fibonacci numbers is defined by recurrence relation, then we can easily use recursion to achieve its calculation.

As the calculation of factorial, the bigger of the numerical calculation, the more times of recursion, and the number of redundant recursion will growth in a redundant geometric way, the efficiency of program will also be lower and lower (you can modify the program, personally test it). So you need according to the actual situation, and make a decision between readability and efficiency.

Example: Print 10 Fibonacci numbers. Use recursion to achieve it.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace Fibonacci
{
    class Program
    {
        public long Fibonacci(int n)
        {
            if (n > 0 && (n == 1 || n == 2))
            {
                return 1;
            }
            else
            {
                return Fibonacci(n - 1) + Fibonacci(n - 2);
            }
        }
 
        static void Main(string[] args)
        {
            Program p = new Program();
            for (int i = 1; i < 11; i++)
            {
                Console.Write(p.Fibonacci(i));
            }
        }
    }
}

Algorithm, C# Algorithm, C#, Programing