【原创】对递归算法的理解

深夜摔键盘

递归的思想很重要。有的问题也只有使用递归的思想才可以求解，比如汉诺塔问题。
递归算法的机理：递归是一个函数对自身对自身的调用。一个函数在进程中某处被调用时，分为前置处理，执行指令，后置处理三个过程。
  
前置处理：系统会首先将寄存器EBP中的数据，返回地址，还有函数需要的参数统统压入系统堆栈保存，然后修改当前程序指针，使其指向函数的入口地址。
  
执行指令：接下来就开始执行该函数中的各条指令
  
后置处理：函数执行结束时，系统要将系统堆栈保存的数据弹出，并修改程序指针，使其指向堆栈中弹出的返回地址，继续执行进程中其他指令。
  
递归程序可以划分为两步骤来实现。
①第一个步骤是前递。只实现自身对自身调用时的前置处理，即不断的进行压栈，所以系统的堆栈的大小随着前递的次数呈线性趋势上升。每一次的前递，都相当于通知系统要完成一个任务，只让系统知道该任务的存在，并不立即让它去执行，而且还要让系统明白要处理这个任务，必须先处理下一个任务。递归可以看作是对一个大任务的进行上下级的分解，下级任务的完成是上级任务完成的保证！
②第二个步骤是回归。当将任务分解到最小单位时，这就满足了回归的条件。此时系统的堆栈相当于一份任务书，程序开始由下而上处理每一层的任务，每完成一个下级任务都要向系统报告，由系统确认该任务完成，然后就将任务规划表中与该任务相关的事宜注销掉。这样直至所有任务处理完毕后，进程中的程序指针会指向由进程第一次递归程序前置处理中压入堆栈的返回地址，去接受新的任务。
  
通过这个分析过程，可以粗略计算一个递归程序需要多大的系统堆栈。如果发生溢出，则要考虑将递归改成非递归的。非递归也是递归，只是原来有系统处理的堆栈被人工设置的堆栈取代了

dragondancing

goodluckwu

深夜摔键盘

qbasic

深夜摔键盘

linduyu_y

goodluckwu

深夜摔键盘

kangarooxy