CH13_递归

本章目标

  • 掌握递归的概念
  • 掌握递归的用法
  • 熟悉常用的递归算法案例

递归

概念

任何一个方法既可以调用其他方法又可以调用自己,而当这个方法调用自己时,我们就叫它递归函数或者递归方法!

特点

1.递归方法一直会调用自己直到某些条件满足,也就是说一定要有出口;

2.递归方法会有一些参数,而它会把这些新的参数值传递给自己;(自己调自己);

递归案例

累加求和

输入一个正整数，求其累加和。

1
2
3
4
5
6
7
8
9
10
11
12
/// <summary>
   /// 求和
   /// </summary>
   /// <param name="num"></param>
   /// <returns></returns>
   static int GetSum(int num)
   {
       if (num == 1)
           return num;
       else
           return num + GetSum(num-1);
   }
1
2
3
4
5
6
static void Main(string[] args)
    {
        Console.WriteLine(GetSum(5));

        Console.ReadLine();
    }

阶乘案例

阶乘(!)是小于某个数的所有正整数的乘积;

注意:0既不是正整数,又不是负整数;0是整数;

0!=1

1!=1

2!=2*1!=2

3!=3*2!=6

4!=4*3!=24

5!=5*4!=120

…

n!=n*(n-1)!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/// <summary>
  /// 阶乘
  /// </summary>
  /// <param name="n"></param>
  /// <returns></returns>
  static long Factorial(int n)
  {

      if (n == 0)
      {

          return 1;
      }
      else
      {
          return n * Factorial(n - 1);
      }

  }

斐波那契额数列

Fibonacci数列是按以下顺序排列的数字:

1,1,2,3,5,8,13,21,34,55….

我们不难发现数列的排列规律是:后一个数加上前一个数,以此类推;

如果F0=0并且F1=1那么Fn=F(n-1)+F(n-2);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/// <summary>
   /// 斐波那契额数列
   /// </summary>
   /// <param name="n"></param>
   /// <returns></returns>
   static long Fabinacci(int n)
   {

       if (n == 0 || n == 1)
       { 

           return n;

       }

       return Fabinacci(n - 2) + Fabinacci(n - 1);  //　　返回值

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

    Console.ReadLine();
}

课后作业

1.略