C#中递归的实现（最大公约数）

(2009-12-30 23:28:29)

标签： 算法 递归 杂谈

分类： 算法

关于递归算法的实现，网上有很多的例子。我今天想举一个计算两个数的最大公约数的例子来说明一下递归算法的用法。首先说明一下的是两个数的最大公约数必然是两数之差与另一个数的公约数（两数不可相等差为正数）下边是源代码

using System;

using System.Collections.Generic;

using System.Text;

 

namespace ConsoleApplication10

{

     class Program

     {

         static void Main(string[] args)

         {

              string  a = Console.ReadLine();

             string  b=Console.ReadLine();

              int aa = Convert.ToInt16(a);

              int bb = Convert.ToInt16(b);

              Maxdivisor maxdivisor = new Maxdivisor();

              int d=maxdivisor.clac(aa, bb);

              Console.WriteLine(d.ToString());

 

         }

     }

     class Maxdivisor

     {

         public int clac(int a,int b)

         {

              if (a == b)return a;

              if (a < b)

              {

                  return clac(a, b - a);//调用函数clac同时也要等待返回值。

              }

              else

              {

             return   clac(a - b, b);

              }            

         }

     }

}

总结递归的用法,可以用一句话来形容，“层层递进，原路返回”，正如上边的程序所示。每次调用clac(int a,int b),方法时，只要a,b的值不相等就会继续调用clac(int a,int b)，这叫做层层递进。但clac(int a,int b)函数是要返回值的，如果没有得到返回值，函数就会被挂在那里，等待着返回值，有了函数才能算执行完毕，程序才能往下继续执行。在层层递进地过程中，当a和b的值相等的时候递进就结束了。返回了一个具体的值。这时就到了”原路返回”的时候了.由于刚才挂起的函数都在等返回值。所以一旦有了返回值函数要一个一个的退出，本着先进后出的原则一个一个的给它的上级函数一个返回值最后当退到int d=maxdivisor.clac(aa, bb);时 d就是我们所要的结果。