栈还有一个重要应用是在程序设计中实现递归。递归是计算机 科学和数学中一种解决问题的及其重要的方法。在数据结构中，可以用它来设计简单。易于理解的算法，特别是在一些具有递归定义的结构上设计算法。
递归的概念
一个直接或间接地调用自己的函数，称作递归函数。递归是程序设计中一个强有力的方法。
递归函数和运行时栈
栈还有一个重要应用就是在程序设计语言中实现函数调用。当一个函数在运行期间调用另一个函数时，在运行被调用函数之前，系统需要将实际参数和返回值地址等数据传递给被调函数，当函数调用时，这些数据与局部变量一起构成一条“工作记录”，被压入系统提供的栈。
下面用一个简单的阶乘函数的执行过程来说明递归与栈的关系。描述如下：
1 int fact(int w) 2 { 3 if(w==0) 4 return 1; 5 else 6 t=fact(w-1) 7 return (w*t); 8 }
递归算法的设计方法
递归时解决复杂问题的一种有效方法。如果掌握了递归算法的设计思路，就能比较容易地解决一类复杂的问题。但是什么样的问题可以用递归来解决呢？如何设计递归算法呢？
一般来说，如果一个复杂的问题能够被分解成若干个同类型的子问题，那么这个问题可以用递归算法实现。
在设计递归算法时，应该遵循下面的规则：
①定义一个最小规模的问题，并给出其解。
②把复杂的问题划分为同类型的若干规模较小的子问题 ，并分别解决子问题。
③把各子问题旳解组合起来，即可得到原问题的解。
例如：汉诺塔问题：
1 void Hanoi(int n,char A,char B,char C) 2 { 3 if(n>0) //n=0是最小子问题，不做任何动作，直接退出 4 { 5 Hanoi(n-1,A,C,B); //子问题①：将A上面的n-1个盘子移到B上 6 Move(A,n.C); //将编号为n的圆盘从A移到C 7 Hanoi(n-1,B,A,C); //子问题②：将B上的n-1个盘子移到C上 8 } 9 }
递归算法的分析
利用递归使我们设计算法和编程都非常简单，可读性高。但是往往导致算法效率比较低。
这体现了算法的简单性与效率之间的矛盾。
用Fibonacci数列来说明这个问题。
1 long Fib(int n) 2 { 3 if(n==1||n==2) 4 return 1; 5 else 6 return Fib(n-1)+Fib(n-2); 7 }
从调用情况来看，相同实参的同一个函数被调用了多次。求Fib(6)时，Fib(3)被调用了3次，Fib(2)被调用了5次，总共调用的次数为15次。算法时间复杂度为O(2n)。
为了便于比较，下面给出非递归算法解决Fibonacci问题。
1 long FibIter(int n) 2 { 3 long oneback,twoback,current; 4 oneback=1; 5 twoback=1; 6 7 if(n==1||n==2) 8 return 1; 9 else 10 { 11 for(int i=0;i<n;i++) 12 { 13 current=oneback+twoback; 14 twoback=oneback; 15 oneback=current; 16 } 17 } 18 return current; 19 }
很显然，以上算法当n>=3时，时间复杂度是n-2，远小于递归算法的时间复杂度。
需要注意的是，在使用递归时必须权衡设计简单与算法的时间和空间复杂度的关系，再有足够并且效率要求不高的情况下可以使用递归。