数据结构&算法 递归基础

• 

  递归

  某些计算机编程语言允许模块或函数自行调用。这种技术称为递归。递归地，函数α要么直接调用自身，要么调用函数β，后者依次调用原始函数α。函数α称为递归函数。

  示例 - 一个调用自身的函数。

  
  int function(int value) {
     if(value < 1)
        return;
     function(value - 1);
  
     printf("%d ",value);   
  }
  

  示例 - 一个函数调用另一个函数，该函数又再次调用它。

  
  int function1(int value1) {
     if(value1 < 1)
        return;
     function2(value1 - 1);
     printf("%d ",value1);   
  }
  int function2(int value2) {
     function1(value2);
  }
  

• 

  属性

  递归函数可以像循环一样无限循环。为了避免无限运行递归函数，递归函数必须具有两个属性-

  • 基本标准 -必须至少有一个基本标准或条件，以便在满足此条件时，该函数停止递归调用自身。
  • 渐进方法 -递归调用应以每次进行递归调用时都更接近基本标准的方式进行。
• 

  实现

  许多编程语言都通过堆栈来实现递归。通常，每当一个函数（调用者）调用另一个函数（被调用者）或其本身作为被调用者时，调用者函数就会将执行控制权转移给被调用者。此传输过程还可能涉及一些要从呼叫者传递到被呼叫者的数据。这意味着，调用者函数必须暂时中止其执行，并在执行控件从被调用者函数返回时稍后恢复。在这里，调用者函数需要从其搁置状态的执行点完全开始。它还需要与正在使用的数据完全相同的数据值。为此，为调用者功能创建一个激活记录（或堆栈框架）。

  

  激活记录保留有关局部变量，形式参数，返回地址以及传递给调用者函数的所有信息。
• 

  递归分析

  有人可能会争论为什么要使用递归，因为可以通过迭代来完成相同的任务。第一个原因是，递归使程序更具可读性，并且由于最新增强的CPU系统，递归比迭代更有效。
• 

  时间复杂度

  在迭代的情况下，我们采用迭代次数来计算时间复杂度。同样，在递归的情况下，假设一切都是恒定的，我们尝试找出进行递归调用的次数。对函数的调用为Ο（1），因此进行递归调用的（n）次使递归函数为Ο（n）。
• 

  空间复杂度

  空间复杂度被计算为模块执行所需的额外空间量。在迭代的情况下，编译器几乎不需要任何额外的空间。编译器会不断更新迭代中使用的变量的值。但是，在进行递归的情况下，每次进行递归调用时，系统都需要存储激活记录。因此，可以认为递归函数的空间复杂度可能会高于具有迭代函数的空间复杂度。