目录 一用栈实现递归二双层递归转栈三栈模拟递归函数调用

【目录】

一、 用栈实现递归 2 二、 双层递归转栈 4 三、 栈模拟递归函数调用 5

一、用栈实现递归

#include<stack> #include <iostream> using namespace std; /*利用递归实现1.2.3......n的排列输出*/ int printN(int n) { if (n>0) { cout << n; return printN(n - 1); } } /*利用栈实现1.2.3......n的排列输出*/ void printNS_shunxu(int n) { stack<int> mystack; AAA: if (n > 0) { mystack.push(n); while (!mystack.empty()) { cout << mystack.top(); mystack.pop(); } n -= 1; goto AAA; } } /*自己改进：利用栈实现1.2.3......n的排列输出*/ void printNS_shunxu(int n) { stack<int> mystack; while( n != 0 || !mystack.empty() ){ if( n!=0 ) { mystack.push( n-- ) ; } if( !mystack.empty() ){ cout << mystack.top() << " " ; mystack.pop() ; } } } void printNS_nixu(int n) { stack<int> mystack; while( n!=0 || !mystack.empty() ) { while( n!=0 ) { mystack.push( n-- ) ; } while( !mystack.empty() ){ cout << mystack.top() << " " ; mystack.pop() ; } } } void printNS_nixu(int n) { stack<int> mystack; AAA: if (n > 0) { mystack.push(n); n -= 1; goto AAA; } while (!mystack.empty()) { cout << mystack.top(); mystack.pop(); } } /*递归：实现1到n之间的累加*/ int get100(int i) { if (!i) { return 0; } else { return get100(i - 1) + i; } } /*栈：实现1到n之间的累加*/ int getN(int i) { stack<int> mystack; int res = 0; AA: if (i) { mystack.push(i); i--; goto AA; } while (!mystack.empty()) { res += mystack.top(); mystack.pop(); } return res; } void to2(int num) { if (num) { cout << num % 2; to2(num / 2); } } void main () { cout << get100(100) << endl; printNS_nixu(9); printNS_shunxu(9); cout<<"\n"<<getN(100)<<"\n"; to2(10); cin.get(); }

二、双层递归转栈

#include<iostream> #include <stack> using namespace std; /*递归实现斐波那契序列*/ int getF(int n) { if (n==1 ||n==2) { return 1; } else { return getF(n - 1) + getF(n - 2); } } /*数组实现斐波那契序列*/ int GetFF(int n) { int *p = new int[n]; p[0] = p[1] = 1; for (int i = 2; i < n;i++) { p[i] = p[i - 1] + p[i - 2]; } return p[n - 1]; } /*栈实现斐波那契序列*/ int GetFFF(int n) { stack<int> mystack; int f1, f2, f3; f1 = f2 = 1; int i = 2; ABC: if (i<n) { mystack.push(f1); mystack.push(f2); f3 = 0; while (!mystack.empty()) { f3+= mystack.top(); mystack.pop(); } //f3 = f2 + f1; f1 = f2;//轮替 f2 = f3; i++; goto ABC; } return f3; } /*for循环轮替实现斐波那契序列*/ int GetFFFF(int n) { int f1, f2, f3; f1 = f2 = 1; for (int i = 2; i < n; i++) { f3 = f2 + f1; f1 = f2;//轮替 f2 = f3; } return f3; } void main() { cout << getF(10) << endl; cout << GetFF(10) << endl; cout << GetFFF(10) << endl; cin.get(); }

三、栈模拟递归函数调用

#include<iostream> #include <stack> //递归，有顺序，逆序，栈吃一个吐一个，顺序，一次吃完再吐，逆序 //递归，数据保留中间结果，函数指针保留操作 //汉诺塔，斐波那契数列 递归计算表达式 ，栈， using namespace std; void printN(int n) { if (n > 0) { cout << n; return printN(n - 1); } } struct datas { int n; void(*p)(int); }; void print(int n) { cout << n; } //1+100 void printall(int n) { stack<datas> mystack; AAA: if (n > 0) { datas s1; s1.n = n; s1.p = print; mystack.push(s1); while (!mystack.empty()) { datas stemp = mystack.top(); stemp.p(stemp.n); mystack.pop(); } n -= 1; goto AAA; } } void main() { printall(10); cin.get(); }