函数的嵌套调用
 
Python语言允许在函数定义中出现函数调用，从而形成函数的嵌套调用，如例所示。
 
 在例中，第6行在fun2()函数中调用fun1()函数，程序执行时会跳转到fun1()函数处去执行，执行完fun1()后，接着执行fun2()函数中剩余的代码，如图所示。
 
 函数的递归调用
 
在函数的嵌套调用中，一个函数除了可以调用其他函数外，还可以调用自身，这就是函数的递归调用。递归必须要有结束条件，否则会无限地递归（Python默认支持997次递归，多于这个次数将终止）。
 
接下来演示函数的递归调用，如例所示。
 
 在例中，第10行到第12行定义f()函数用于计算阶乘。当n == 0时，程序立即返回结果，这种简单情况称为结束条件。如果没有结束条件，就会出现无限递归。当n > 0时，就将这个原始问题分解成计算n – 1阶乘的子问题，持续分解，直到问题达到结束条件为止，就将结果返回给调用者，然后调用者进行计算并将结果返回给它自己的调用者，该过程持续进行，直到结果返回原始调用者为止。原始问题就可以通过将f(n-1)的结果乘以n得到，这种调用过程就称为递归调用，如图所示。
 

递归的风险
 
实际开发中应避免使用递归，原因主要两点：
 
1. 递归调用在深度上不可预测，层数过多不断压栈，可能会引起栈溢出的崩溃；
 2. 不容易理解；
 
 
 
栈溢出
 
stack overflow异常是程序中常常会碰到的，原因是调用线程栈不够用。windows默认栈大小是1M，使用栈空间超过了1M就会报出stack overflow异常。
 
产生原因
 
1、死循环
 
出现了死循环，例如：递归函数没有出口，不管栈空间多大必定溢出。
 
long  func(int n)
 {
      return n*func(n-1);
 }
 
这是个没有出口的递归函数， 必然引起栈溢出。纠正：
 
long func(int n)
 {
      if(n==1)   return 1;
      return   n*func(n-1);
 }
 
2、栈确实不够用
 
存到栈上的主要内容是：局部变量和函数调用的函数环境，包括函数参数等。
 
局部变量，例如：
 
char buff[1024*1024]
 
buff为1M，如果你的栈默认也是1M大小，这就会发生栈溢出，因为其他东西会占掉少量栈空间，局部变量能用的空间肯定小于1M，程序在执行到main函数之前，就会跳出stack overflow异常。
 
3、函数调用层数太深
 
这种情况一般发生在递归调用中
 
过多的递归调用为什么会引起栈溢出呢？
 
在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当程序执行进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，就会导致栈溢出。函数的参数是通过stack栈来传递的，在调用中会占用线程的栈资源。递归调用在到达最后的结束点后，函数才能依次退栈清栈，如果递归调用层数过多，就可能导致占用的栈资源超过线程的最大值，从而导致栈溢出，程序异常退出。
 
不得不使用递归的场景：遍历一个目录下的所有文件，包括其子目录的文件。
 对于解决一些包含重复类似逻辑的问题，递归对于开发人员来说是清晰的选择。
 
在不得不使用递归时，如何评估栈空间是否足够，避免栈溢出。
 
评估思路：
 
1. 确认当前线程栈空间限制是多少？
 
2. 递归调用n次，分析n次压栈后栈空间的损耗是多少？
 
3. 结合业务预估最大可能的递归调用次数，如果大于或已经接近栈大小, 就存在栈越界风险，需要放大栈空间或者做功能规格约束。
 
优化
 
当栈不够使用时，一种办法是修改程序：
 
主要还是要注意递归调用引起的栈溢出，多数情况可以通过算法优化来解决：
 
1、控制递归深度。例如，使用动态规划来代替递归算法等。
 
2、修改栈的大小。
 
 
 
尾递归优化
 
尾递归是指，在函数返回的时候，调用函数本身，并且return语句不能包含表达式。如果递归调用，都出现在函数的末尾，这个递归函数就是尾递归的函数。
 
尾递归函数的特点是在回归过程中，不用做操作，这个特性很重要，因为大多数现代编译器会利用这一特点，自动生成优化的代码。
 有些语言极力提倡尾递归，因为它们的编译器会对代码进行优化，不会因为递归次数的增加，给函数栈带来巨大的开销。
 
尾递归优化，使无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。
 
递归的优点是逻辑清晰。
 
 
 
循环替代递归
 
所有的递归都可以改写成循环的方式。 
 
斐波那契数列： 1，1，2，3，5，......
 求斐波那契数列的第N项的值
 
尾递归和循环的执行效率都非常高。但是尾递归的递归层数大到一定程度会出现段错误。尾递归的函数栈开销比普通递归要小的多，执行效率大很多。 但是尾递归仍然有函数栈开销。
 正因为尾递归具有函数栈开销，其调用次数比循环小很多。
 
实现一个功能，能不用递归就别用递归，能用尾递归就用尾递归。
 
 //一般递归
int fib_normal(int n)
{
    if (n <= 2)
        return 1;
    else
        return fib_normal(n-1) + fib_normal(n-2);
}
 
//尾递归
int fib_rail(int n, int first,  int second)
{
    if (n == 1) return first;
    if (n == 2) return second;
    return fib_rail(n-1, second, second+first);
}
unsigned int fib_rail_rec(unsigned int n)
{
    return fib_rail_rec(n, 1, 1);
}
 
// 循环取代递归
int fib_no(int n)
{
    if (n <= 2)
        return 1;
    int x=1, y=1, y_tmp=0;
    for (int i=0; i<n-2; i++)
    {
        y_tmp = y;
        y = x+y;
        x = y_tmp;
    }
    return y;
}
 
栈溢出windbg显示Stack overflow
 
0:072> !analyze -v
 
CONTEXT:  (.ecxr)
 eax=0000000e ebx=76fbceb8 ecx=00413fb8 edx=00417b98 esi=00413fb8 edi=00000000
 eip=76ed83eb esp=2f652ffc ebp=2f653040 iopl=0         nv up ei pl nz ac pe nc
 cs=0023  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00010216
 ntdll!RtlAcquireSRWLockExclusive+0xb:
 76ed83eb 53              push    ebx
 Resetting default scope
 
EXCEPTION_RECORD:  (.exr -1)
 ExceptionAddress: 76ed83eb (ntdll!RtlAcquireSRWLockExclusive+0x0000000b)
    ExceptionCode: c00000fd (Stack overflow)
   ExceptionFlags: 00000000
 NumberParameters: 2
    Parameter[0]: 00000001
    Parameter[1]: 2f652ff8
  
 


  

 
       在java语言中，使用递归调用时，如果过多的调用容易造成
 java.lang.StackOverflowError即栈溢出和程序执行过慢
 。这是一个潜在Bug和影响程序执行效率问题，需要谨慎使用。
 
 
 

  
 
 
 
 

  下面先看造成java.lang.StackOverflowError即栈溢出问题：
 
 
 

   
  
 
   
 
    
 
     [java] 
     view plain
      copy 
     
 
     
 
     
    
 
   
 
   
 public class RecursionTest  
 {  
   
     public static void recursion(int totalTimes,int time)  
     {  
         if(totalTimes > 1)  
         {  
             System.out.println("这是第 " +  time + "次调用！");  
             totalTimes--;  
             time++;  
             recursion(totalTimes, time);  
         }  
         else  
         {  
             System.out.println("调用结束，共调用了" + time + "次");  
             return;  
         }  
     }  
       
     public static void main(String[] args)  
     {  
         int totalTimes = 1000000;  
         int time = 1;  
         long startTime = System.currentTimeMillis();  
         System.out.println("嵌套调用起始时间：" + startTime);  
         recursion(totalTimes, time);  
         System.out.println("嵌套调用结束时间：" + System.currentTimeMillis());  
         System.out.println("总耗时：" + (System.currentTimeMillis() - startTime));  
         System.out.println("------------------------------------------------------------");  
     }  
   
 }  
 
  
 修改“totalTimes”，当到达一定值时，报如下错误：
 
 
 

  
 
 
 
 

  在开发时，要注意避免该问题，特别是递归过多调用时，最好改为for或者whlie来代替。
 
 
 

  如下cycle()方法：
 
 
 

   
  
 
   
 
    
 
     [java] 
     view plain
      copy 
     
 
     
 
     
    
 
   
 
   
 public static void cycle(int totalTimes, int time)  
 {  
     if(totalTimes > 1)  
     {  
         System.out.println("这是第 " +  time + "次调用！");  
     }  
     else  
     {  
         System.out.println("调用结束，共调用了" + time + "次");  
     }  
 }  
 
  
 代替recuresion()方法：
 
 
 

   
  
 
   
 
    
 
     [java] 
     view plain
      copy 
     
 
     
 
     
    
 
   
 
   
 public static void recursion(int totalTimes,int time)  
     {  
         if(totalTimes > 1)  
         {  
             System.out.println("这是第 " +  time + "次调用！");  
             totalTimes--;  
             time++;  
             recursion(totalTimes, time);  
         }  
         else  
         {  
             System.out.println("调用结束，共调用了" + time + "次");  
             return;  
         }  
     }  
 
  
 
  
 
  
 
  
 
   
 
    
 
     [java] 
     view plain
      copy 
     
 
     
 
     
    
 
   
 
   
   
 
  
 
 
 
 

  再看一下对程序执行效率的影响：
 
 
 

  仍然使用上面的例子，分别cycle()方法和在main()方法中加入如下代码：
 
 
 

   
  
 
   
 
    
 
     [java] 
     view plain
      copy 
     
 
     
 
     
    
 
   
 
   
 startTime = System.currentTimeMillis();  
 System.out.println("循环调用起始时间：" + startTime);  
 for (int index = totalTimes; index > 0; index--)  
 {  
     cycle(index, time);  
     time++;  
 }  
 System.out.println("循环调用结束时间：" + System.currentTimeMillis());  
 System.out.println("总耗时：" + (System.currentTimeMillis() - startTime));  
 System.out.println("--------------------  
 
  
 整个代码如下：
 
 
 

   
  
 
   
 
    
 
     [java] 
     view plain
      copy 
     
 
     
 
     
    
 
   
 
   
 public class RecursionTest  
 {  
   
     public static void recursion(int totalTimes,int time)  
     {  
         if(totalTimes > 1)  
         {  
             System.out.println("这是第 " +  time + "次调用！");  
             totalTimes--;  
             time++;  
             recursion(totalTimes, time);  
         }  
         else  
         {  
             System.out.println("调用结束，共调用了" + time + "次");  
             return;  
         }  
     }  
       
     public static void cycle(int totalTimes, int time)  
     {  
         if(totalTimes > 1)  
         {  
             System.out.println("这是第 " +  time + "次调用！");  
         }  
         else  
         {  
             System.out.println("调用结束，共调用了" + time + "次");  
         }  
     }  
       
     public static void main(String[] args)  
     {  
         int totalTimes = 100000;  
         int time = 1;  
         long startTime = System.currentTimeMillis();  
         System.out.println("嵌套调用起始时间：" + startTime);  
         recursion(totalTimes, time);  
         System.out.println("嵌套调用结束时间：" + System.currentTimeMillis());  
         System.out.println("总耗时：" + (System.currentTimeMillis() - startTime));  
         System.out.println("------------------------------------------------------------");  
           
         startTime = System.currentTimeMillis();  
         System.out.println("循环调用起始时间：" + startTime);  
         for (int index = totalTimes; index > 0; index--)  
         {  
             cycle(index, time);  
             time++;  
         }  
         System.out.println("循环调用结束时间：" + System.currentTimeMillis());  
         System.out.println("总耗时：" + (System.currentTimeMillis() - startTime));  
         System.out.println("------------------------------------------------------------");  
     }  
   
 }  
 
  
 
  

   
 
  
 
  

   分别测试totalTimes为500,1000,3000对比结果：
  
 
  

   
 
  
 
  

    
   

    500次：
   
 
   

    
    
 
   
 
   

    
    
 
   
 
   
 
  
 
  

   1000次：
  
 
  
  
 
  
  
 
  
 
 
 
 
 
 

  3000次：
 
 
 

  
  
 
 
 
 

  
  
 
 
 
 

  
 
 
 
 
 
  

   以下是从网络上摘抄的：
  
 
  

   根本原因是这样的,对于每一个线程,都有一个java栈 ,当有一个方法被调用的时候,会产生一些跟这个方法相关的信息,如方法名，参数，中间变量等等,这些叫做栈帧 ,当一个方法执行完毕  这个栈帧才会从栈顶pop掉  你递归的话  会一直向栈里push栈帧  而这个java栈是有一定的长度或深度的,当栈满了,无法再进行push的时候 就出现你上面的异常了,解决办法的话 就不要用递归操作 改用for 而且平时也不建议用递归的,效率太低了 .  
   
 
   
 
   栈溢出了，JVM依然是采用栈式的虚拟机，这个和C和Pascal都是一样的。函数的调用过程都体现在堆栈和退栈上了。你调用构造函数的“层”太多了，以致于把栈区溢出了。  
   
 
   通常来讲，一般栈区远远小于堆区的，因为函数调用过程往往不会多于上千层，而即便每个函数调用需要1K的空间(这个大约相当于在一个C函数内声明了256个int类型的变量)，那么栈区也不过是需要1MB的空间。通常栈的大小是1－2MB的。通常递归也不要递归的层次过多，很容易溢出.  
  
 
  

    
   
 
   对java.lang.StackOverflowError的分析：  
   
 
   原因：运行一个程序,JVM会开辟一块内存空间去储存程序进行时的某些信息,当程序运行时需要储存的信息超过了分配的空间,就会出现那样的问题.比如死循环,  
   
 
   解决：首先从程序代码优化方面着手，检查是否有死循环、递归等程序，如果有，修正、优化相关代码。  
  
 
 
 

我在上一篇文章中已经为读者对于函数的概念以及它的使用开了一个头，本文的目的是让读者进一步更加深入的了解C++中的函数部分。
 
首先我先将上一章内容最后的每日一练附上答案：
 
#include <iostream>
using namespace std;

bool isprime(int n)   // 实现对素数的判断
{
    bool prime = true;
    if (n == 1)
    {
        return false;
    }
    for (int i = 2; i <= n - 1; i++)  //从2 到 n - 1进行判断 
    {                                   //其实读者大可不必这样，判断到根号n也可以，还能降低程序的运行时间
        if (n % i != 0)
        {
            prime = true;
        }
        else
        {
            prime = false;
            break;
        }
    }
    return prime;
}

int main()    //主函数部分实现输出1-10000以内的素数
{
    for (int i = 1; i <= 10000; i++)
    {
        if (isprime(i))
        {
            cout << i << " ";
        }
    }
    return 0;
}
 
好了，以上是上期每日一练的答案，有问题的小伙伴可以私信作者哦！
 
好，回到正题，首先我们继续讨论一下关于函数的调用，首先，如果有多个函数，函数是允许在自身中调用其他的函数的，这叫做函数的嵌套调用，调用别的函数的函数叫做主调函数，被别的函数调用的函数叫做被调函数，其实这个很好理解的，其实上面的答案就可以看出来了，我们在主函数main（）中调用了我们自己写的函数isprime（），这个时候main函数就叫做主调函数，而我们自己写的函数就叫做被调函数了，这其实就是个简单的概念，读者需要了解就足够了。
 
无独有偶，既然函数可以调用别的函数，那么请读者思考一下，函数能调用自身吗？
 
很明显，这是允许的，我们把函数调用自身的情况叫做递归调用，我们从下面的一个实例来了解一下递归调用：
 
我们知道，斐波那契数列的第n项为前两项之和，即  Fn = Fn-1 + Fn-2，并且F1 = 1，F2 = 1，此时，我们就可以写一个函数来计算斐波那契数列的第n项的值，代码如下：
 
int f(int n)
{
    if (n == 1 || n == 2)
    {
        return 1;
    }
    else
        return f(n - 1) + f(n - 2);
}
 
我们来分析一下这段代码，首先第一行的if，如果n为1或者n为2，那么函数直接返回一个具体的值，否则就返回前两项之和，读者可以想一下，比如说我们要计算第五项的和，即f（5），那我们是不是要计算f（4）+f（3），那么，f（4）又会继续分解为f（3）+ f（2），直到f（3）分解为f（1）+ f（2），这时，我们已经知道了f（1）和f（2）的值，就可以往回算出f（3）从而继续算出f（4）的值，最后就可以得到f（5）的值，这就是我们的目标答案，我们可以发现，在计算f（5）的时候分为了两个步骤，首先将f（5）不断拆分，直到得到f（1）和f（2），并且我们知道f（1）和f（2）的值，这时候在往回算，我们把类似将f（5）不断拆解为f（4）+f（3）的这个过程叫做递推，，把从f（1）开始往前算的这个过程叫做回归，事实上，所谓递归，就是由递推和递归两个部分组成，先不断递推，在往回回归，这样就构成了一个完整的递归过程。
 
诺有读者在刚开始接触递归的话，一定要注意一下几点：
 
首先，递归算法一定要有一个递归边界，何为递归边界呢，例如上面的例子中，if（n == 1 || n == 2）return 1；这个就是递归边界，也就是说递推的过程到n为1或n为2时就停止了，没有递归边界的递归算法是没有意义的，因为没有递归边界的话，递归算法就不会停止，可以说是一个死循环。
 
所以我们说递归算法是有穷的。
 
讲到这里，请读者思考一下，递归算法有没有缺陷呢？
 
答案是：有！！！！
 
为什么？
 
首先，我们先来讲一下递归的好处，递归符合人思考的过程，通过递归思想写出来的代码可读性强，有些问题如果没有使用递归，那么写出来的代码将及其难看。
 
现在我们来讲一下递归的缺陷，那就是程序的效率低，首先，我们知道，递归是在函数中调用它本身，那么每调用一次，系统就会不断给重新调用的函数开辟新的空间，只要运行的次数一多，程序的运行效率就会急转直下，读者可以自己去试一下，计算第100项，或者第1000项，这时候程序很有可能会崩溃。那么，有没有解决的办法呢？
 
答案是有的，这个方法就叫记忆话递归。
 
还是上面斐波那契数列的例子，我们不难看出，当我们计算f（5）的时候，就要计算f（4）和f（3），计算f（4），又要计算f（3）和f（2）的值，可以看到，这里f（3）被计算了两次，所以，记忆化递归的原理就在这里，我们将计算过的值储存起来，这样下次在计算到这个值的时候，我们就可以直接使用，这样，程序的效率就会大大提升。代码实现如下：
 
bool vis[10000];  //用于判断该数是否被计算过
int dp[10000];    //用于储存目标数字和中间被计算过的数
int f(int n)
{
    if (n == 1 || n == 2)
        return 1;
    if (vis[n]) return dp[n];
    vis[n] = true;
    return dp[n] = f(n - 1) + f(n - 2);
}

int main()
{
    int n;
    cin >> n;
    cout << f(n);
    return 0;
}
 
首先，这里可能会有读者有疑问，这个vis数组什么用？其实bool型数组的初值都为假，读者可以取带入几个数字去深入体会一下，因为记忆化递归在处理动态规划的问题时也有极大的作为。
 
好了，以上是本期的全部内容了，有问题的小伙伴可以私信博主哦。
 
一下是每日一练
 
利用递归算法完成汉诺塔问题。（在输出是打印出移动过程）
 
答案在下期公布。