在自己实现了内存中顺序存储和链式存储的栈结构之后,有的同学可能还是有一些疑问。既然都是线性表,我们为什么不直接使用顺序表或链表,反而要创造出一种特殊的线性表呢?

    其实答案很简单,通过我们规定了特殊规则之后的线性表,能够更轻松地完成很多工作。在本篇博客中我就来给大家介绍一下,栈的一个重要的作用——在程序设计语言中实现递归。

    首先我们先要明白什么是递归?

    简单来说,在高级编程语言中,一个函数直接调用自己或者通过其它语句间接调用自己的函数,这个函数就是递归函数。

    因为递归函数能够一直调用自己,所以我们必须得提供一个清晰的出口条件,使得递归函数在满足某个条件后停止调用,否则程序将进入死循环无穷无尽的递归下去。

    下面我们就一起来看一个递归的例子:

    同学们是否还记得阶乘的概念?

    对于任何大于等于1 的自然数n 阶乘表示方法为:a9efdf45b9dd4a9ab2deee5b8e2fd486-ae51f3deb48f8c545a6331063e292df5e0fe7f63.jpg

    0的阶乘等于1: 0!=1

    那么如果现在要求我们提供一个实现阶乘的函数,我们应该如何做呢?

    	public  static int factorial(int param) {
    		if(param <0 ) throw new IllegalArgumentException("invalid param");
    		if(param == 0) return 1;
    		int fac = 1;
    		for(int i =1; i<=param; i++) {
    			fac *= i;
    		}
    		return fac;
    	}
    

    如果我们使用递归来实现阶乘函数的话

    	public static int recFactorial(int param) {
    		if(param <0 ) throw new IllegalArgumentException("invalid param");
    		if(param == 0) return 1;
    		return param*recFactorial(param-1);
    	}
    

    在上面的方法中 if(param ==0) return 1 就是我们函数的出口。

    假设我们传入的param = 3, 因为3>0, 所以返回 3×recFactorial(2)

    recFactorial(2) 中param =2, 因为2>0, 所以返回 2×recFactorial(1)

    recFactorial(1) 中param =1, 因为1>0, 所以返回 1×recFactorial(0)

    recFactorial(0) 中param =0, 所以 recFactorial(0) = 1;

    那么recFactorial(3) = 3×recFactorial(2) = 3×(2×recFactorial(1)) = 3×((1×recFactorial(0))) = 3×2×1×1 = 6;

    现在我们来分析一下上面两种不同方法实现的阶乘函数,第一种采用的是循环的结构,不需要反复调用函数;第二种递归结构,使程序看起来更容易让人理解,就像是将我们要解决的问题翻译成了代码一样,但是由于需要不停的调用函数本身,所以会对消耗大量的内存空间(主要消耗栈空间)。

    到这里,大家可能会好奇了,讲了这么多的递归跟我们的栈又有什么关系呢?为什么说递归是栈结构的应用呢?

    这主要是因为对于进程而言,程序能直接访问的内存被分为了5个部分:代码区,数据区,堆区和未使用区。代码区中是用来存放我们编写的程序被编译后的机器码(二进制),在程序运行过程中是无法被修改的,具有只读和固定大小的特点。数据区中存放了应用程序中的全局数据,静态数据和一些常量字符串等。堆 是运行时程序动态申请的空间,属于程序运行时直接申请、释放的内存资源。栈区用来存放函数的传入参数、临时变量,以及返回地址等数据。未使用区是分配新内存空间的预备区域。

    其中,栈区被设计成具备栈数据结构后进先出特点的内存空间。而函数调用的过程就是将函数参数,返回值等压入栈中栈帧的过程。而递归本质上就是函数调用其本身,因此该函数会一次次被压入栈区中,直到到达递归程序的出口条件时,栈顶的栈帧(满足跳出条件的那一次函数调用)会被弹出,同时该函数的返回值也会被新的栈顶栈帧获得并当作参数继续使用。

    关于内存原理的更详细分析,请关注博主的《深度剖析内存系列》