下载文档原格式
递归函数的非递归实现递归函数是一种非常常见的编程技巧，但是在某些情况下，递归函数可能会导致栈溢出等问题。
因此，我们可以通过非递归的方式来实现递归函数。
首先，我们需要了解递归函数的本质：递归函数是一种自我调用的函数，每次调用都会将当前的状态保存在栈中，并等待递归结束后依次弹出栈帧，恢复调用时的状态。
因此，非递归实现递归函数的核心思想就是利用栈来保存状态，模拟递归时的栈帧。
具体实现方法如下：1. 把递归函数中的自我调用转换为循环调用，并使用栈来保存每次调用的参数和状态。
2. 每次循环调用时，将参数和状态入栈，并更新参数和状态。
3. 循环调用结束时，从栈中弹出上一个状态，恢复参数和状态。
例如，假设我们要实现一个阶乘函数：```pythondef factorial(n):if n == 1:return 1else:return n * factorial(n-1)```我们可以使用非递归的方式来实现：```pythondef factorial(n):stack = [(n, 1)]res = 1while stack:num, acc = stack.pop()res *= accif num > 1:stack.append((num-1, num))return res```在这个实现中，我们使用栈来保存每次调用的状态，每次循环调用时，将参数和状态入栈，并更新参数和状态。
循环调用结束时，从栈中弹出上一个状态，恢复参数和状态。
最终得到阶乘的结果。
总的来说，非递归实现递归函数可以避免栈溢出等问题，同时也可以提高代码的执行效率。
但是，非递归实现递归函数可能会影响代码的可读性和维护性，需要根据具体情况进行权衡。
⼀、什么是递归 很多数据结构的定义都是根据递归性质来进⾏定义的，是因为这些结构固有的性质。
递归是指某个函数直接或间接的调⽤⾃⾝。
问题的求解过程就是划分成许多相同性质的⼦问题的求解，⽽⼩问题的求解过程可以很容易的求出，这些⼦问题的解就构成⾥原问题的解了。
⼆、递归的⼏个特点 1.递归式，就是如何将原问题划分成⼦问题。
2.递归出⼝，递归终⽌的条件，即最⼩⼦问题的求解，可以允许多个出⼝。
3.界函数，问题规模变化的函数，它保证递归的规模向出⼝条件靠拢 三、递归的运做机制 很明显，很多问题本⾝固有的性质就决定此类问题是递归定义，所以递归程序很直接算法程序结构清晰、思路明了。
但是递归的执⾏过程却很让⼈费解，这也是让很多⼈难理解递归的原因之⼀。
由于递归调⽤是对函数⾃⾝的调⽤，在⼀次调⽤没有结束之前⼜开始了另外⼀次调⽤，按照作⽤域的规定，函数在执⾏终⽌之前是不能收回所占⽤的空间，必须保存下来，这也就意味着每⼀次的调⽤都要把分配的相应空间保存起来。
为了更好管理这些空间，系统内部设置⼀个栈，⽤于存放每次函数调⽤与返回所需的各种数据，其中主要包括函数的调⽤结束的返回地址，返回值，参数和局部变量等。
其过程⼤致如下： 1.计算当前函数的实参的值 2.分配空间，并将⾸地址压栈，保护现场 3.转到函数体，执⾏各语句，此前部分会重复发⽣(递归调⽤) 4.直到出⼝，从栈顶取出相应数据，包括，返回地址，返回值等等，收回空间，恢复现场，转到上⼀层的调⽤位置继续执⾏本次调⽤未完成的语句。
四、引⼊⾮递归 从⽤户使⽤⾓度来说，递归真的很简便，对程序宏观上容易理解。
递归程序的时间复杂度虽然可以根据T(n)=T(n-1)*f(n)递归求出，其中f(n)是递归式的执⾏时间复杂度，⼀般来说，时间复杂度和对应的⾮递归差不多，但是递归的效率是相当低的它主要发费在反复的进栈出栈，各种中断等机制上(具体的可以参考操作系统)更有甚者，在递归求解过程中，某些解会重复的求好⼏次，这是不能容忍的，这些也是引⼊⾮递归机制的原因之⼀。
栈的应用递归到非递归的转换张 铭 北京大学信息学院1内容提要递归函数调用原理 机械的递归转换 优化后的非递归函数 非递归的二叉树周游2张铭 北京大学信息学院递归函数示例void exmp(int n, int& f) { int u1, u2; if (n<2) f = n+1; else { exmp((int)(n/2), u1); exmp((int)(n/4), u2); f = u1*u2; } } 张铭3北京大学信息学院数学公式fu (n) ={n +1当n < 2时fu ( ⎣n / 2 ⎦)* fu ( ⎣n / 4 ⎦)n ≥ 2时}4张铭 北京大学信息学院函数调用及返回的步骤调用– 保存调用信息（参数，返回地址） – 分配数据区（局部变量） – 控制转移给被调函数的入口返回– 保存返回信息 – 释放数据区 – 控制转移到上级函数（主调用函数）5张铭 北京大学信息学院函数执行过程图解二叉树图解 Exmp(7,&f) f=u1*u2=4u1=f=2 u2=f=2 Exmp(3,&f) Exmp(1,&f) f=u1*u2=2u1=f=2 Exmp(1,&f)张铭u2=f=1 Exmp(0,&f)6北京大学信息学院用栈模拟递归调用过程后调用，先返回(LIFO），所以用栈rd=1: n=1 f=1 u1=? u2=? f=2 rd=2: n=0 f=? u1=? u2=? f=? rd=2: n=1 f=? u1=2 u2=1 rd=1: n=3 f=? u1=? u2=? f=2 u1=? u2=? rd=3: n=7 f=? u1=? u2=? u1=2 u2=2张铭7北京大学信息学院递归过程的模拟假设 void recfunc(p1, p2, p3，…，pk, pk+1, …, pm) 是一个递归函数void是无返回值型的函数，如果有返回值， 我们可以把返回值转换为一个引用型参数 其中参数p1, p2, p3，…，pk是值传递，参 数pk+1, …, pm是引用传递。
c语言递归函数的非递归实现递归函数是指在函数内部调用自身的函数，这种函数调用方式能够简化问题的表达和解决。
但是在实际编程中，递归函数可能会消耗大量的系统资源，因此有时候需要将递归函数改写为非递归形式，以减少资源消耗。
接下来将介绍如何在C 语言中实现递归函数的非递归形式。
一种常见的方法是使用栈来模拟递归函数的调用过程。
在递归函数中，每次调用都会将函数的参数、局部变量和返回地址保存在栈中，而函数执行完毕后会从栈中取出这些信息以便返回上一层调用。
因此，我们可以自己创建一个栈来模拟这个过程。
首先，我们需要定义一个结构体来表示栈的节点，包括函数的参数、局部变量和返回地址等信息。
接着，我们可以创建一个栈，用来保存这些节点。
在非递归函数中，我们首先将函数的初始参数压入栈中，然后开始一个循环，每次循环中执行函数的一次递归调用。
在调用函数时，我们将函数的参数和局部变量保存在一个节点中，然后将这个节点压入栈中。
当函数执行完毕后，我们从栈中弹出这个节点，取出其中的参数和局部变量，以便返回上一层调用。
通过这种方式，我们可以在不使用递归的情况下实现递归函数的功能。
这样一来，我们可以减少系统资源的消耗，提高程序的效率。
当然，这种方法在一些情况下可能会增加代码的复杂性，但在需要避免递归调用的情况下，这是一种可行的替代方案。
总的来说，非递归实现递归函数的方法是使用栈来模拟函数调用的过程，将函数的参数、局部变量和返回地址保存在栈中，以便在函数执行完毕后能够返回上一层调用。
通过这种方式，我们可以在不消耗过多系统资源的情况下，实现递归函数的功能。
这种方法在一些情况下可能会增加代码的复杂性，但是在需要避免递归调用的情况下，是一种有效的解决方案。
递归函数解释
一、递归定义
递归函数是指一个函数在其定义域内，存在某个或某些子集作为其自身的输入，也就是一个函数直接或间接调用自身的一种过程。
通常递归函数的定义会包含两部分：基本情况和递归情况。
二、基本情况
基本情况也被称为基线条件，是递归函数的结束条件。
基本情况决定了递归何时停止，它必须是直接可求解的情况。
基本情况是递归函数的根，其他递归情况都由它导出。
三、递归转化
递归转化是将问题转化为更小的同类问题的一种策略。
在递归函数中，每一个递归调用都是为了解决一个更小的子问题，以便于通过这些子问题的解来找到原问题的解。
四、递归终止
递归终止是指函数在完成一系列递归调用后，最终达到基本情况并返回结果的过程。
递归终止是递归函数的终点，也是递归函数开始返回结果的地方。
五、递归层次
递归层次是指函数在执行过程中所经历的递归深度。
每一个递归调用都会增加一层的递归深度，直到达到基本情况并返回结果，然后开始逐层返回，直到完成所有递归调用。
理解递归层次有助于更好地理解递归函数的执行过程和时间复杂度。
递归算法向非递归算法转换递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。
对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。
因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。
将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。
前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。
1. 直接转换法直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。
尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。
例如求阶乘的递归算法：long fact(int n){if (n==0) return 1;else return n*fact(n-1);}当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。
对于尾递归形式的递归算法，可以利用循环结构来替代。
例如求阶乘的递归算法可以写成如下循环结构的非递归算法：long fact(int n){int s=0;for (int i=1; i<=n;i++)s=s*i; //用s保存中间结果return s;}单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。
显然，尾递归是单向递归的特例。
例如求斐波那契数列的递归算法如下：int f(int n){if (n= =1 | | n= =0) return 1;else return f(n-1)+f(n-2);}对于单向递归，可以设置一些变量保存中间结构，将递归结构用循环结构来替代。
递归与非递归转换的基础知识是能够正确理解三种树的遍历方法：前序，中序和后序，第一篇就是关于这三种遍历方法的递归和非递归算法。
一、为什么要学习递归与非递归的转换的实现方法?1>并不是每一门语言都支持递归的。
2>有助于理解递归的本质。
3>有助于理解栈，树等数据结构。
二、三种遍历树的递归和非递归算法递归与非递归的转换基于以下的原理：所有的递归程序都可以用树结构表示出来。
需要说明的是，这个”原理”并没有经过严格的数学证明，只是我的一个猜想，不过在至少在我遇到的例子中是适用的。
学习过树结构的人都知道，有三种方法可以遍历树：前序，中序，后序。
理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处，所以我们先来谈谈这个。
需要说明的是，这里以特殊的二叉树来说明，不过大多数情况下二叉树已经够用，而且理解了二叉树的遍历，其它的树遍历方式就不难了。
1>前序遍历a>递归方式：void preorder_recursive(Bitree T> /* 先序遍历二叉树的递归算法 */{if (T> {visit(T>。
/* 访问当前结点 */preorder_recursive(T->lchild>。
/* 访问左子树 */preorder_recursive(T->rchild>。
/* 访问右子树 */}}b>非递归方式void preorder_nonrecursive(Bitree T> /* 先序遍历二叉树的非递归算法 */initstack(S>。
push(S,T>。
/* 根指针进栈 */while(!stackempty(S>> {while(gettop(S,p>&&p> { /* 向左走到尽头 */visit(p>。
/* 每向前走一步都访问当前结点 */push(S,p->lchild>。
递归算法修改为非递归算法1.引言1.1 概述递归算法是一种常见的计算方法，它通过将大问题拆分成一个或多个相似的子问题来解决。
递归算法通常通过不断调用自身来处理这些子问题，直到达到基本情况时停止递归。
递归算法的设计具有简洁、优雅的特点，并在某些情况下能够提供高效的解决方案。
然而，递归算法也存在一些局限性。
首先，递归调用会带来额外的函数调用开销，可能会导致程序运行速度较慢。
其次，递归算法对于大规模问题的解决可能会导致堆栈溢出的问题，因为每一次递归调用都需要在内存中保存一些信息。
为了克服递归算法的局限性，我们可以将其修改为非递归算法。
非递归算法使用迭代的方式来解决问题，通过使用循环结构来代替递归调用，从而降低了函数调用的开销。
此外，非递归算法更加直观易懂，可以减少程序的复杂性。
本文将探讨递归算法修改为非递归算法的必要性和优势，并通过具体的例子和算法讲解，详细介绍如何将递归算法转化为非递归算法的思路和方法。
通过对比和分析，我们将展示非递归算法在某些情况下的效率和可行性，以及它在解决问题时的优势和不足。
在接下来的章节中，我们将首先介绍递归算法的特点，包括递归调用和基本情况的判断。
然后，我们将讨论非递归算法的优势，包括降低函数调用开销和提高程序运行效率的能力。
最后，我们将总结递归算法的局限性，强调修改为非递归算法的必要性。
1.2 文章结构本文分为引言、正文和结论三个部分。
在引言部分，我们将概述本文的主题和目的，并介绍文章的结构。
在正文部分，我们将首先探讨递归算法的特点，包括递归算法的定义、实现方式和应用场景等。
然后我们将分析非递归算法的优势，包括非递归算法相对于递归算法的效率、可读性和内存消耗等方面的优势。
接下来，在结论部分，我们将讨论递归算法的局限性，包括递归算法在处理大规模数据时存在的问题和栈溢出的风险等。
最后，我们将强调修改为非递归算法的必要性，以解决递归算法的局限性，并总结本文的主要观点和结论。
通过以上结构，我们将全面而系统地探讨递归算法修改为非递归算法的背景、原因和优势，以及非递归算法在解决问题中的应用价值。
