C ｜对函数调用和递归调用（递归，回归）的深入了解

当一个函数调用另一个函数时，不是将被调用函数的所有代码复制到内存中，而是使用代码共享方法. 也就是说，它们都是调用同一函数的代码，并且系统为每个调用打开一组存储单元，以存储该调用的返回地址和被中断函数的参数值. 这些单元以堆栈的形式存储，每个调用一次被推入堆栈. 执行返回时，将执行堆栈操作，将保留在当前堆栈顶部的值返回到相应的参数以进行恢复，并使用堆栈顶部的返回地址来断开连接.

如果存在以下简单示例: （为了理解嵌套的复杂关系，则简单的问题被故意复杂化了）

运行效果:

调用堆栈的情况:

递归函数（recursive function）或递归调用（recursion）是通过判断选择（递归条件）连续调用自身，并可以通过初始条件返回评估. 这是嵌套函数调用的一种特殊情况. 大多数编程语言都支持递归操作，例如C \ C ++.

简而言之，

递归算法是函数调用函数本身以完成算法设计的一种方法. 这是一个子问题，将问题变成了类似的尺寸减小问题. 然后递归调用函数（或过程）以指示问题的解决方案.

递归函数实际上只知道如何解决最简单的情况，即所谓的基本情况. 如果调用该函数来解决基本情况，那么它将仅返回结果. 如果调用函数来解决更复杂的问题，则通常将问题分为两个概念部分: 一个部分是函数知道如何执行的部分，另一部分是函数不知道如何执行的部分. 为了使递归起作用，后一部分必须与原始问题相似，但相对简单一些或稍小一些. 这个新问题看起来与原始问题非常相似，因为该函数启动（调用）自身的全新副本来解决此问题-这是递归调用，也称为递归步骤.

可以实现递归，因为函数的每个执行过程在堆栈上都有自己的形式参数和局部变量副本，而这些副本与该函数的其他执行过程无关. 这种机制是大多数当代编程语言实现子程序结构的基础，并使递归成为可能. 假设被调用函数调用了一个被调用函数，然后假定该被调用函数又调用了该调用函数. 第二个调用称为调用函数的递归，因为它发生在调用函数的当前执行完成之前. 此外，由于原始调用函数和当前调用函数在堆栈的较低位置具有独立的参数和参数集，因此原始参数和变量将不会受到影响，因此递归可以正常进行. 程序遍历这些功能的执行过程称为递归下降.

程序员需要确保递归函数不会随机更改静态变量和全局变量的值，以避免递归下降期间上层函数的错误. 程序员还必须确保存在终止条件，以结束递归下降过程并返回顶层.

I可以将需要解决的问题转化为一个或多个要解决的子问题，这些子问题的解决方法与原始问题完全相同，但数量和规模不同.

II递归调用的数量必须受到限制；

III必须具有初始条件和递归条件. 前一种条件用于终止递归和撤退；

I的定义是递归的. 递归的概念有很多数学公式，序列和定义c 函数的递归调用，例如阶次系统n !、斐波那契数列等；

II数据结构是递归的. 如单链表，二叉树遍历等；

III问题的解决方案是递归的. 例如Vano塔的问题.

正整数的阶乘是小于或等于该数字的所有正整数的乘积，0的阶乘为1. 自然数n的阶乘记为n!. 1808年，凯斯顿·卡曼（Keston Kaman）引入了这种表示法.

无符号长阶乘（无符号长号）

{

if（number

回合1；

其他

返回编号*阶乘（number-1）;

}

调用堆栈的情况:

从以上过程可以看出，每次进行递归调用时，都需要将其推入堆栈一次. 每当遇到递归退出并完成执行时，都需要将堆栈卸载一次并恢复参数值. 完成所有执行后，堆栈应为空.

因此，递归调用主要分为两个步骤. 第一步是分解过程c 函数的递归调用，即使用递归体将“大问题”分解为“小问题”，直到递归退出（初始条件）为止，然后进行第二步使用已知的“小问题”来计算“大问题”.

斐波那契兔子问题（斐波那契兔子问题）是意大利数学家Fi-bonacci（L.）在他的著名著作“算法书”中提出的问题. 从一对兔子开始，经过两个月的成长，这些兔子变成了大兔子. 假设每对大兔子每个月可以生产一对兔子，那么一年可以繁殖几对兔子？这个问题导致了著名的级数: 1,1,2,3,5,8,13,21,34,55,89,144，...这是一个线性递归序列.

int fib（int n）

{

如果（n == 1 || n == 2）

返回1；

其他

返回（fib（n-1）+ fib（n-2））;

}

//因为一对兔子可以在出生后两个月进行繁殖，所以第n个月的兔子数是前一个月的兔子数加上繁殖数（表面繁殖数等于前一个月的数量）.

递归算法的调用和回归关系可以使用递归树来表示递归算法执行过程中的分解和评估过程，这是对递归工作堆栈的模拟.

阶乘的递归是在调用多个步骤之后对几个步骤进行的回归评估. 斐波那契的递归更为复杂. 分解调用和回归评估交替进行，重复循环直到找到最终值.

在执行递归函数期间，其形式参数将随着递归调用而改变，但是在每次调用之后，它的形式返回到调用之前的形式参数，并且递归函数的未引用形式参数的值为称为状态（在执行后，递归函数的引用类型参数将传递回实际参数，有时类似于全局变量，而不是状态的一部分），状态将在调用期间发生变化，并且在调用之后自动恢复到通话前状态.

通常使用选择结构来实现递归. 连续调用自身会形成一个循环，因此，如果要结束递归，则必须有一个初始条件才能终止递归，否则将存在无限递归（即无限循环）. 由此也可以理解，所有递归都可以通过迭代（循环）来实现. 如果计算出1到n的总和:

－结束－

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-253563-1.html