从main()里的fun(a)开始分析:
此时s是 字符串a 第一个字符的地址
t = s++;相当于t = s; s++;
s++使得s指向字符串a中的下一个字符。
接着递归调用fun(s);
s 每指向一个字符, 就递归调用一次, 即递归调用进行了5次, s 分别指向 '1', '2', '3', '4', '\0'
fun()里的if(s)相当于if(s != '\0'), 即第五次调用时不会再继续调用新的fun()了,
而是直接返回上一个fun()
这时s指向 '4', 即 a[3];
接着依次执行第4, 3, 2, 1个fun()的
if(t!='\0') putchar(t);
因此在屏幕上打印出4321
最后返回到main(),
退出程序
如何用栈实现递归与非递归的转换
分类： C/C++2010-07-12 14:4012人阅读评论(0)收藏举报
如何用栈实现递归与非递归的转换一为什么要学习递归与非递归的转换的实现方法 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);
}
pop(S,p);
if(!stackempty(S)) { / 向右走一步 /
pop(S,p);
push(S,p->;rchild);
}
}
}
复制代码
2)中序遍历 a)递归方式
void inorder_recursive(Bitree T) / 中序遍历二叉树的递归算法 /
{
if (T) {
inorder_recursive(T->;lchild); / 访问左子树 /
visit(T); / 访问当前结点 /
inorder_recursive(T->;rchild); / 访问右子树 /
}
}
复制代码
b)非递归方式
void inorder_nonrecursive(Bitree T)
{
initstack(S); / 初始化栈 /
push(S, T); / 根指针入栈 /
while (!stackempty(S)) {
while (gettop(S, p) && p) / 向左走到尽头 /
push(S, p->;lchild);
pop(S, p); / 空指针退栈 /
if (!stackempty(S)) {
pop(S, p);
visit(p); / 访问当前结点 /
push(S, p->;rchild); / 向右走一步 /
}
}
}
复制代码
3)后序遍历 a)递归方式
void postorder_recursive(Bitree T) / 中序遍历二叉树的递归算法 /
{
if (T) {
postorder_recursive(T->;lchild); / 访问左子树 /
postorder_recursive(T->;rchild); / 访问右子树 /
visit(T); / 访问当前结点 /
}
}
复制代码
b)非递归方式
typedef struct {
BTNode ptr;
enum {0,1,2} mark;
} PMType; / 有mark域的结点指针类型 /
void postorder_nonrecursive(BiTree T) / 后续遍历二叉树的非递归算法 /
{
PMType a;
initstack(S); / S的元素为PMType类型 /
push (S,{T,0}); / 根结点入栈 /
while(!stackempty(S)) {
pop(S,a);
switch(amark)
{
case 0:
push(S,{aptr,1}); / 修改mark域 /
if(aptr->;lchild)
push(S,{aptr->;lchild,0}); / 访问左子树 /
break;
case 1:
push(S,{aptr,2}); / 修改mark域 /
if(aptr->;rchild)
push(S,{aptr->;rchild,0}); / 访问右子树 /
break;
case 2:
visit(aptr); / 访问结点 /
}
}
}
复制代码
4)如何实现递归与非递归的转换 通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递 给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调 函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数 所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的 ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存 就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现 同步 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行回到上 面说的树的三种遍历方式,抽象出来只有三种 *** 作:访问当前结点,访问左子树,访问右子树这三 种 *** 作的顺序不同,遍历方式也不同如果我们再抽象一点,对这三种 *** 作再进行一个概括,可以 得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次 处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式) 下面以先序遍历来说明:
void preorder_recursive(Bitree T) / 先序遍历二叉树的递归算法 /
{
if (T) {
visit(T); / 访问当前结点 /
preorder_recursive(T->;lchild); / 访问左子树 /
preorder_recursive(T->;rchild); / 访问右子树 /
}
}
复制代码
visit(T)这个 *** 作就是对当前数据进行的处理, preorder_recursive(T->;lchild)就是把当前 数据变换为它的左子树,访问右子树的 *** 作可以同样理解了 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行关键在于一下三个地方:a) 确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结 构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用 树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的 "叶子结点" 三三个例子 好了上面的理论知识已经足够了,下面让我们看看几个例子,结合例子加深我们对问题的认识 即使上面的理论你没有完全明白,不要气馁,对事物的认识总是曲折的,多看多想你一定可以明 白(事实上我也是花了两个星期的时间才弄得比较明白得) 1)例子一:
f(n) =n + 1; (n <2)
f[n/2] + f[n/4](n >;= 2);
这个例子相对简单一些,递归程序如下:
int f_recursive(int n)
{
int u1, u2, f;
if (n < 2)
f = n + 1;
else {
u1 = f_recursive((int)(n/2));
u2 = f_recursive((int)(n/4));
f = u1 u2;
}
return f;
}
复制代码
下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的首先,什么是叶子结点 ,我们看到当n < 2时f = n + 1,这就是返回的语句,有人问为什么不是f = u1 u2,这也是一个 返回的语句呀答案是:这条语句是在u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))之后 执行的,是这两条语句的父结点 其次,什么是当前结点,由上面的分析,f = u1 u2即是父结点 然后,顺理成章的u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))就分别是左子树和右子 树了最后,我们可以看到,这个递归函数可以表示成后序遍历的二叉调用树好了,树的情况分析 到这里,下面来分析一下栈的情况,看看我们要把什么数据保存在栈中,在上面给出的后序遍历的如果这个过程你没 非递归程序中我们已经看到了要加入一个标志域,因此在栈中要保存这个标志域;另外,u1,u2和 每次调用递归函数时的n/2和n/4参数都要保存,这样就要分别有三个栈分别保存:标志域,返回量 和参数,不过我们可以做一个优化,因为在向上一层返回的时候,参数已经没有用了,而返回量也 只有在向上返回时才用到,因此可以把这两个栈合为一个栈如果对于上面的分析你没有明白,建 议你根据这个递归函数写出它的递归栈的变化情况以加深理解,再次重申一点:前期对树结构和 栈的分析是最重要的,如果你的程序出错,那么请返回到这一步来再次分析,最好把递归调用树和 栈的变化情况都画出来,并且结合一些简单的参数来人工分析你的算法到底出错在哪里 ok,下面给出我花了两天功夫想出来的非递归程序(再次提醒你不要气馁,大家都是这么过来 的)
int f_nonrecursive(int n)
{
int stack[20], flag[20], cp;
/ 初始化栈和栈顶指针 /
cp = 0;
stack[0] = n;
flag[0] = 0;
while (cp >;= 0) {
switch(flag[cp]) {
case 0: / 访问的是根结点 /
if (stack[cp] >;= 2) { / 左子树入栈 /
flag[cp] = 1; / 修改标志域 /
cp++;
stack[cp] = (int)(stack[cp - 1] / 2);
flag[cp] = 0;
} else { / 否则为叶子结点 /
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 1: / 访问的是左子树 /
if (stack[cp] >;= 2) { / 右子树入栈 /
flag[cp] = 2; / 修改标志域 /
cp += 2;
stack[cp] = (int)(stack[cp - 2] / 4);
flag[cp] = 1;
} else { / 否则为叶子结点 /
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 2: / /
if (flag[cp - 1] == 2) { / 当前是右子树吗 /
/
如果是右子树, 那么对某一棵子树的后序遍历已经
结束,接下来就是对这棵子树的根结点的访问
/
stack[cp - 2] = stack[cp] stack[cp - 1];
flag[cp - 2] = 2;
cp = cp - 2;
} else
/ 否则退回到后序遍历的上一个结点 /
cp--;
break;
}
}
return stack[0];
}
复制代码
算法分析:a)flag只有三个可能值:0表示第一次访问该结点,1表示访问的是左子树,2表示 已经结束了对某一棵子树的访问,可能当前结点是这棵子树的右子树,也可能是叶子结点b)每 遍历到某个结点的时候,如果这个结点满足叶子结点的条件,那么把它的flag域设为2;否则根据 访问的是根结点,左子树或是右子树来设置flag域,以便决定下一次访问该节点时的程序转向 2)例子二 快速排序算法 递归算法如下:
void swap(int array[], int low, int high)
{
int temp;
temp = array[low];
array[low] = array[high];
array[high] = temp;
}
int partition(int array[], int low, int high)
{
int p;
p = array[low];
while (low < high) {
while (low < high && array[high] >;= p)
high--;
swap(array,low,high);
while (low < high && array[low] <= p)
low++;
swap(array,low,high);
}
return low;
}
void qsort_recursive(int array[], int low, int high)
{
int p;
if(low < high) {
p = partition(array, low, high);
qsort_recursive(array, low, p - 1);
qsort_recursive(array, p + 1, high);
}
}
复制代码
需要说明一下快速排序的算法: partition函数根据数组中的某一个数把数组划分为两个部分, 左边的部分均不大于这个数,右边的数均不小于这个数,然后再对左右两边的数组再进行划分这 里我们专注于递归与非递归的转换,partition函数在非递归函数中同样的可以调用(其实 partition函数就是对当前结点的访问) 再次进行递归调用树和栈的分析: 递归调用树:a)对当前结点的访问是调用partition函数;b)左子树: qsort_recursive(array, low, p - 1);c)右子树:qsort_recursive(array, p + 1, high); d)叶子结点:当low < high时;e)可以看出这是一个先序调用的二叉树 栈:要保存的数据是两个表示范围的坐标
void qsort_nonrecursive(int array[], int low, int high)
{
int m[50], n[50], cp, p;
/ 初始化栈和栈顶指针 /
cp = 0;
m[0] = low;
n[0] = high;
while (m[cp] < n[cp]) {
while (m[cp] < n[cp]) { / 向左走到尽头 /
p = partition(array, m[cp], n[cp]); / 对当前结点的访问 /
cp++;
m[cp] = m[cp - 1];
n[cp] = p - 1;
}
/ 向右走一步 /
m[cp + 1] = n[cp] + 2;
n[cp + 1] = n[cp - 1];
cp++;
}
}
复制代码
3)例子三 阿克曼函数:
akm(m, n) = n + 1; (m = 0时)
akm(m - 1, 1); (n = 0时)
akm(m - 1, akm(m, n - 1)); (m != 0且n != 0时)
复制代码
递归算法如下:
int akm_recursive(int m, int n)
{
int temp;
if (m == 0)
return (n + 1);
else if (n == 0)
return akm_recursive(m - 1, 1);
else {
temp = akm_recursive(m, n - 1);
return akm_recursive(m - 1, temp);
}
}
按照你的要求编写的Java递归程序如下:
import javautilScanner;public class GGG {
public static void main(String[] args) {
int N = 0;
Scanner sc=new Scanner(Systemin);
int num=scnextInt();
for(int n=0;n<num;n++){
N=scnextInt();
int a[]=new int[N];
for(int i=0;i<alength;i++){
a[i]=scnextInt();
}
Systemoutprint("case "+(n+1)+":");
process(a,0);
Systemoutprintln();
}
}
private static void process(int[] a, int n) {
if(n==0){
if(isPrime(a[n+1]))
Systemoutprint(1+" ");
else
Systemoutprint(0+" ");
}else if(n==alength-1){
if(isPrime(a[n-1]))
Systemoutprint(1+" ");
else
Systemoutprint(0+" ");
return;
}else{
if(isPrime(a[n-1])&&isPrime(a[n+1]))
Systemoutprint(2+" ");
else if(isPrime(a[n-1])||isPrime(a[n+1]))
Systemoutprint(1+" ");
else
Systemoutprint(0+" ");
}
process(a,n+1);
}
public static boolean isPrime(int num) {
int i;
for(i=2;i<num;i++){
if(num%i==0)
break;
}
if(i==num){
return true;
}
return false;
}
}
运行结果:
2
5
5 7 2 9 13
case 1:1 2 1 2 0
3
10 4 5
case 2:0 1 0
首先，这段程序将w的初始值设为3，这个楼主应该清楚，然后看这段代码
if ( w != 0) //递归结束条件
{
print (w-1);
for (i = 1; i <= w; ++i)
printf ("%d ", w);
printf ("\n");
}
这段代码首先判断w是否为0，很显然，w为3，所以执行
print (w-1);
这句，执行这句则返回到第二步void print (int w)；
w-1变成2，没有输出；然后继续向下执行，又到
print (w-1);
这句，跟上边一样，又返回到第二步，这样w依次减到0，这个过程根本没涉及到for循环。这样程序运行到最后的分号，则返回刚才w=1的情况，然后执行
print (w-1);这句后边的程序，现在w=1，执行for循环，输出一个1，然后程序返回到w=2的那步，执行for循环，输出两个2，然后返回w=3那步，执行for循环，输出三个3；递归函数很特别的，所以楼主要好好学哦！！
毛病出在循环上：
For i = 1 To 3
n = n + 1
DebugPrint "n=" & n
If n = 2 Then Exit Sub
Test
Next i
如果去掉循环，程序是可以结束的。
有了循环，如果改为If n = 2 Then End
也能结束。
不改的话，它退出的只是当前一轮的调用。还有未结束的调用，它继续运行。由于 是n先加1，再判断，所以它就自动绕过了退出的机会。
如果改成下面这样，也是可以正常退出的：
Private Sub Test()
Dim i As Long
For i = 1 To 3
DebugPrint "n=" & n
If n = 2 Then Exit Sub
n = n + 1
Test
Next i
End Sub
def power(x, y):
if(y):
print("y="+str(y))
return xpower(x,y-1)
else:
print("y="+str(y)+",y为false已退出")
return 1
print("结果为",power(2,2))
"""
首先这个函数作用就是算出x的几次方
Python程序语言指定任何非0和非空（null）值为true，0 或者 null为false。
递归，就是在运行的过程中调用自己。
构成递归需具备的条件：
1 子问题须与原始问题为同样的事，且更为简单；
2 不能无限制地调用本身，须有个出口，化简为非递归状况处理。
函数解释
一开始传入两个参数时 假设传入2和2 power(2,2)
进入到power函数中那么这里面的x=2,y=2
如果y为true就是y>0的时候
就返回 xpower(x,y-1)中
在这个返回值又调用一次power(x,y)
此时就是2power(2,1)
这个时候y依旧为true,y>0
在这个返回值又调用一次power(x,y)
此时return 2power(2,0)
这个时候y为零就为false，返回了个1回去
这时候我们return 2power(2,0)就相当于return 21
然后上面的return 2power(2,1)这里的power函数的返回值就是上面返回来的2，那么这里就是return 22
最后再返回给power(2,2)中
得到结果为4
"""
运行结果：
y=2
y=1
y=0,y为false已退出
结果为 4
以上就是关于大家给我讲解下这个递归调用的程序啊，它到底是怎么调用的呢全部的内容，包括:大家给我讲解下这个递归调用的程序啊，它到底是怎么调用的呢、怎样用递归的方法遍历栈、JAVA这道题要如何用递归实现呢，求大神等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）