经验分享 - 数据结构与算法(九) - V2CE

雪里已知春信至，寒梅点缀琼枝腻。

在学习其他算法之前,我们要先看一下”递归算法”,许多问题如果用递归来解,会出乎意料的简单,也就是上文中说的代码小巧精炼.

我们先来看下面的代码:

private void Blash ()
{
   Blash();
}

这段代码是什么意思呢?函数自己调用了自己,那么这样下去会没完没了的调用下去,其实,函数自己调用自己就是”递归”,但是这种无条件一直调用自身的递归是很危险的,也就是死循环.但是话又说回来,如果递归用的好的话,能帮我们解决一些棘手的问题.

递归还是循环?

现在我们来看一个实际的问题,倒序输出0-5,那么这个就很简单了.用循环来做的话是这样:

for (int i = ;i >=; i--;)
{
  Debug.Log (i);
}

这么写当然一点问题都没有,但是本文是来介绍递归的,所以说用递归,我们该怎么写呢?

void TimeCut (int timer)
{
  Debug.Log (timer);
  TimerCut (timer-1);
}

下面来分析这段代码是如何运行的

首先调用此函数的时候,传入一个值,首先代码打印出传入的值,然后调用自身,也会传入一个值,但是这个值已经被减去了1,所以下一次打印的是减去1的值.如果带入具体的值,第一次打印的是5,第二次打印的是4,…以此类推.

这里并没有循环语法,但是实现了和循环一样的功能,事实上,循环体大部分都可以用递归来改写,但是,能改不代表有必要去改.上面的对比只是演示了可以,并没有演示怎么巧妙.在看到它巧妙之前,我们还要看清它的运作方式.

如果你足够细心,你也应该发现,上面的递归是个有问题的程序,因为只要是循环,就应该有条件跳出.但是上面的递归并没有写这个跳出条件,当然这并不是我忘了,而是要介绍一个重要的概念:”基准情形”,那么什么叫基准情形呢?在递归中,不用递归的情形就叫做基准情形,那么对于上面的递归函数,加个判断条件:

if (timer <)
{
   return;
}

那么当timer<0的时候就称之为基准情形.

阶乘

阶乘是最适合用来讲递归算法的,比如5的阶乘是5*4*3*2*1= 120.

要会阶乘,首先得学会看,然后学会写.那么5得阶乘用代码怎么写呢?

static BigInteger myFatorFun2(BigInteger n)
        {
            if (n == )
                return ;
            BigInteger temp = myFatorFun2(n - ) * n;
            Debug.Log("计算结果是：" + temp.ToString());
            return temp;
        }

第一点,得要看到基准情形,那么这里的基准情形代码中已经体现了.就是当n=0的时候. 然后反着看,也就是说当n=1的时候程序在做什么,再看n=2的时候程序做什么.但是计算机中却不是这样.

那么,我们模拟计算机中看到此程序做了哪些操作.
首先我们模拟调用了此函数,并传入了5.第一步进入程序的时候首先是判断基准情形不满足,然后程序向下走,到了给temp赋值的这一句,那么给temp赋值这里就是递归了,但是递归是有条件的,那就是形参要减一.

那么要想获得形参减一的函数返回值,那么就必须再次走一遍程序,也许你看的出来,这个就好像俄罗斯套娃,你要想看到结果就必须把套完拆开,还好这个程序循环次数不长,那么如果很长的话那么我们还真不一定能看出来.所以这里有个图的讲解.

首先形参为5,带入

myFatorFun2(5)

到了程序中有递归, myFatorFun2(n – 1) * n;这里的形参减一了,

所以就会变成得先计算出myFatorFun2(4)的值才行

myFatorFun2(5)	myFatorFun2(4)

那么计算myFatorFun2(4)的时候里面又递归了,得计算myFatorFun2(3)的值才行.

myFatorFun2(5)	myFatorFun2(4)	myFatorFun2(3)

又发现计算myFatorFun2(3)的值得要计算myFatorFun2(2)的值才行

myFatorFun2(5)	myFatorFun2(4)	myFatorFun2(3)	myFatorFun2(2)

其余的我就不写了,其实到这里你应该看得出来,这些很像上文中讲的栈,事实上,程序的方法体就是存在栈中的.这里的递归就是在到基准情形时,从栈中一个一个的取出来计算值.

所以前文中说的无限递归,也就是死循环的那样,它就会一直申请内存空间,知道计算机的内存耗尽导致栈溢出,或者是计数的超出规定范围导致程序奔溃等.

总结

本文只对递归做了一个简单的介绍,具体使用在下篇文章中写,也许你并未领略到递归好在哪,也许你觉得递归只是代码精炼了一些,但是可读性完全没有循环那么顺畅.

事实上,递归比较适合运用与一些不知道计算深度的运算,比如有点unity基础的,你用递归去寻找某个物体的子物体,但是你不知道有几层,那么你就可以通过Getchild(0)是否可读取到来作为一个判断的基准情形.掌握了递归,你就掌握了一批高效但是更为高深的算法,它们都离不开递归的原理.

…END…

经验分享 – 数据结构与算法(九)

总结