求讲解下递归的思路。 - C# 论坛

已结贴√ 问题点数：10 回复次数：6

求讲解下递归的思路。

class Program
    {
        static void Main(string[] args)
        {
            int[] a = new int[] { 3, 12, 24, 36, 55, 68, 75, 88 };
            Program p = new Program();
            //调用方法(数组a,查找75,起始下标0,结束下标为数组最后值的下标)
            int b = p.Binsearch(a, 75, 0, a.Length - 1);
        }

        /// <summary>
        ///
        /// </summary>
        /// <param name="a">待查找数组,需有序排列,升降都可</param>
        /// <param name="key">待查找的值</param>
        /// <param name="low">数组起始下标</param>
        /// <param name="high">数组结束下标</param>
        /// <returns>待查找值的索引</returns>
        public int Binsearch(int[] a, int key, int low, int high)
        {
            if (low > high || high < 0)
            {
                return -1;
            }

            int mid = (low + high) / 2;

            if (key < a[mid])
            {
                return Binsearch(a, key, low, mid - 1);
            }
            else if (key > a[mid])
            {
                return Binsearch(a, key, mid + 1, high);
            }
            else
            {
                return mid;
            }

        }
    }
求版主讲解下递归思路

第 2 楼

得分:10

首先说二分法，以升序数组为例，就是数组中的数从小到大排序
1 数组中取中间那个数，判断跟要找的数是大还是小，中间的数大于要找的数，那么要找的数就在数组的前半段；否则要找的数就在数组的后半段
2 取数组的一半（要么前半段，要么后半段），按1的方式继续找，直到找到

由此可以看出，每一次查找，所用的方式都是一样的，重复相同的方法，只是待查找的数组在慢慢缩小，这里是用下标去改变数组的大小

既然每次所用的方式是一样的，那么，在程序中同一个方法就可以完成任务，只是每一次传进去的数组不一样而已，也就是参数会有变化，但方法是同一个方法

那么，程序中判断到数组在前半段或是后半段之后，调用同样的方法，参数变一下，就可以完成下一次的查找，一直到找到结果

程序的关键在于设定跳出循环的条件

－－－－－－－－－－－－－－－－－－－－－－－
本身自己调用自己，是个无限的循环，但是设定了退出条件，就不是无限循环了

举个再简单一点的例子
private int FindNum(int num)
{
    if(num <= 0)
    {
        return 0;
    }
    else
    {
        return FindNum(num - 1);
    }
}

调用该方法int i = FindNum(2);
程序判断num不是0，进入else ,继续调用FindNum方法，参数变成了2-1,也就是FindNum(1),然后继续进入else，调用FindNum,参数变为0，接着就返回了0

如果把上面例子的递归写成正常的语句,就能看出递归的执行过程
private int FindNum(int num)
{
    if(num <= 0)
    {
        return 0;
    }
    else
    {
        return num - 1;
    }
}
调用int i = FindNum(FindNum(FindNum(2)));

[ 本帖最后由 yhlvht 于 2013-6-14 00:33 编辑 ]