1.Ackermann函数实现
Ackermann 函数的递归特性回顾：
如果 m == 0，返回 n + 1。
如果 m > 0 且 n == 0，返回 Ack(m - 1, 1)。
如果 m > 0 且 n > 0，返回 Ack(m - 1, Ack(m, n - 1))。
在递归实现中，函数调用堆栈保存了每次递归调用的状态。当递归返回时，系统自动恢复到前一个调用状态。为了模拟这种行为，非递归实现使用显式的栈来存储需要恢复的状态。
为什么只对 m 进行压栈弹栈？
1. 关键递归特性：
Ackermann 函数的核心在于 m 的递减和 n 的动态变化。
每次递归调用中，m 是递减的，而 n 的值可能通过嵌套的递归调用变化。
栈的作用是模拟递归调用时需要恢复的状态，而这个状态主要依赖于 m 的变化。m 的变化决定了后续调用的流程，而 n 的变化则是在同一递归调用链中局部调整的。
2. 状态恢复的需求：
对于 m > 0 且 n > 0 的情况，递归调用需要 Ack(m - 1, Ack(m, n - 1))。这意味着 Ack(m, n - 1) 必须先计算，然后再计算 Ack(m - 1, …)。
为了在递归返回时正确恢复状态，必须将当前的 m 保存到栈中，因为在内层递归计算完 Ack(m, n - 1) 后，需要用原来的 m 继续外层的递归计算。
3. n 的局部性：
n 作为局部变量在每一层递归中更新并传递给下一层调用。它不需要恢复到先前的值，因为在每个递归层次中，它要么直接递减（如 Ack(m, n-1)），要么被设为新的值（如 n = 1），所以不需要将 n 的状态保存和恢复。
总结
栈只对 m 进行压栈弹栈 是因为 m 决定了递归的结构和流程，栈通过保存 m 的状态来模拟递归调用的恢复过程。
n 的变化是局部的，它只在当前层次中有意义，并不需要通过栈来恢复。
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stack>
using namespace std;
//递归实现
int Ack(int m,int n)
{
if(m==0)return n+1;
else if(m!=0&&n==0)return Ack(m-1,1);
else return Ack(m-1,Ack(m,n-1));
}
//非递归实现
int Ack1(int m,int n)
{
stack<int>s;
s.push(m);
while(s.empty())
{
if(m==0)
{
n=n+1;
}
else if(n==0)
{
s.push(m-1);
}
else
{
s.push(m-1);//先算内层，先压外层
s.push(m);
n=n-1;
}
}
return n;
}
int main()
{
int m,n;
cin>>m>>n;
cout<<Ack(m,n)<<endl;
}
2.链表递归实现最大值，总和，平均数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
};
Node *CreateListWithTail(int arr[], int n) {
Node*dummy=new Node(-1);
Node*tail=dummy;
for(int i=0;i<n;i++)
{
Node*node=new Node(arr[i]);
tail->next=node;
tail=node;
}
return dummy->next;
}
void print(Node *head)
{
for (Node *p = head; p; p = p->next)
cout << p->val << ' ';
cout << endl;
}
Node* find_max(Node*head)
{
if(!head->next)return head;
Node*max=find_max(head->next);
return max->val>head->val?max:head;
}
int sum(Node*head)
{
if(!head->next)return head->val;
int res=head->val+sum(head->next);
return res;
}
double avg(Node*head,int n) {
if(n==1)return head->val;
double preavg=avg(head->next,n-1);
return (preavg*(n-1)+head->val)/n;
}
int main() {
int a[]={1,2,3,4,5,6};
int n=sizeof(a)/sizeof(int);
Node *head =CreateListWithTail(a, n);
print(head);
Node*max=find_max(head);
cout<<max->val<<endl;
cout<<sum(head)<<endl;
cout<<avg(head,n)<<endl;
return 0;
}
3.
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
void print(int w)
{
if(w!=0)
{
print(w-1);
for(int i=1;i<=w;i++)
{
cout<<w<<" ";
}
cout<<endl;
}
}
void print1(int w)
{
stack<int>s;
while(w>0)
{
s.push(w);
w--;
}
while(s.size())
{
int cur=s.top();
s.pop();
for(int i=0;i<cur;i++)
{
cout<<cur<<" ";
}
cout<<endl;
}
}
int main()
{
print(4);
print1(4);
return 0;
}
4
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
void print(int w)
{
if(w!=0)
{
print(w-1);
for(int i=1;i<=w;i++)
{
cout<<w<<" ";
}
cout<<endl;
}
}
void reverse(int n)
{
cout<<n%10<<" ";
if(n/10!=0)reverse(n/10);
}
void reverse1(int n)
{
stack<int>s;
s.push(n);
while(s.size())
{
int cur=s.top();
s.pop();
cout<<cur%10<<" ";
if(cur/10)s.push(cur/10);
}
}
int main()
{
reverse(582);
reverse1(582);
return 0;
}
5.单链表删除递归
Node* removeALLNodes(Node* head, int x)
{
if(head==NULL)return NULL;
if(head->val==x)return removeALLNodes(head->next,x);//相当于自己执行的下一层的结果直接返回给调用自己的上一层而跳过了自己，达到逻辑删除的效果
//跳过了回溯给自己的这一过程
head->next=removeALLNodes(head->next,x);//具有回溯的过程
return head;
}
1800 52页
第6题
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int max(int a[],int n)
{
if(n==0)return a[0];
if(a[n-1]>max(a,n-1))return a[n-1];
return max(a,n-1);
}
int main()
{
int a[]={1,4,2,5,7,8};
int n=sizeof(a)/sizeof(int);
cout<<max(a,n)<<endl;
return 0;
}
第8题
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stack>
using namespace std;
//递归写法
int gcd(int m,int n)
{
if(m<n)return gcd(n,m);
if(n==0)return m;
else return gcd(n,m%n);
}
//非递归写法(栈消除)
//由于这个 gcd 函数是尾递归，递归调用发生在函数的最后一步
//而且递归调用的结果直接返回给上一层调用，因此不需要保留当前层的状态。每次递归调用的状态可以直接被下一次调用的状态替换，所以栈中的状态可以直接 pop 掉，不需要保存。
int gcd2(int m,int n)
{
stack<pair<int,int>>st;
st.push({m,n});
while(st.size())
{
auto [m,n]=st.top();
st.pop();
if(m<n)
{
st.push({n,m});
continue;
}
if(n==0)return m;
else
{
st.push({n,m%n});
}
}
}
//非递归写法
int gcd3(int m,int n)
{
while(n!=0)
{
if(m<n)
{
swap(n,m);
}
m=m%n;
}
return m;
}
int main()
{
int m,n;
cin>>m>>n;
cout<<gcd3(m,n)<<endl;
return 0;
}
9.汉诺塔非递归
#include <iostream>
#include <stack>
using namespace std;
// 定义一个结构体来保存汉诺塔每次移动的状态
struct HanoiState {
int n; // 盘子数量
char src; // 源柱
char aux; // 辅助柱
char dst; // 目标柱
int stage; // 当前递归阶段
};
void hanoi_non_recursive(int n, char src, char aux, char dst) {
stack<HanoiState> s;
s.push({n, src, aux, dst, 0}); // 初始化状态
while (!s.empty()) {
HanoiState &state = s.top(); // 访问栈顶状态
if (state.n == 1 && state.stage == 0) {
// 如果只剩下一个盘子直接移动
cout << "Move disk 1 from " << state.src << " to " << state.dst << endl;
s.pop(); // 完成移动后弹出状态
} else if (state.stage == 0) {
// 第一步：将 n-1 个盘子从 src 移到 aux
state.stage = 1; // 标记第一阶段完成
s.push({state.n - 1, state.src, state.dst, state.aux, 0});
} else if (state.stage == 1) {
// 第二步：将第 n 个盘子从 src 移到 dst
cout << "Move disk " << state.n << " from " << state.src << " to " << state.dst << endl;
state.stage = 2; // 标记第二阶段完成
} else if (state.stage == 2) {
// 第三步：将 n-1 个盘子从 aux 移到 dst
state.stage = 3; // 标记第三阶段完成
s.push({state.n - 1, state.aux, state.src, state.dst, 0});
} else {
// 所有阶段完成，弹出状态
s.pop();
}
}
}
int main() {
int n;
cout << "Enter the number of disks: ";
cin >> n;
hanoi_non_recursive(n, 'A', 'B', 'C');
return 0;
}
10.第12题
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stack>
using namespace std;
int f(int n)
{
if(n==0)return 1;
if(n>0)
{
return n*f(n/2);
}
}
int f1(int n)
{
stack<int>st;
int res=1;
while(n>0)
{
st.push(n);
n=n/2;
}
while(st.size())
{
res*=st.top();
st.pop();
}
return res;
}
int main()
{
int n;
cin>>n;
cout<<f1(n)<<endl;
return 0;
}
11.ackerman函数
#include <iostream>
#include <stack>
int ackermann(int m, int n) {
// 创建一个栈，保存 m 和 n 的值
std::stack<std::pair<int, int>> st;
st.push({m, n});
// 用于保存计算的结果
int result = 0;
// 模拟递归调用过程
while (!st.empty()) {
auto [m, n] = st.top();
st.pop();
if (m == 0) {
// A(0, n) = n + 1
result = n + 1;
} else if (n == 0) {
// A(m, 0) = A(m - 1, 1)
st.push({m - 1, 1});
} else {
// A(m, n) = A(m - 1, A(m, n - 1))
// 我们需要先计算 A(m, n - 1) 再计算 A(m - 1, result)
st.push({m - 1, -1}); // -1 作为标记，表示等待 A(m-1, result)
st.push({m, n - 1}); // 处理 A(m, n - 1)
}
// 如果栈顶有标记的 -1，表示需要将前一次递归结果传递给 A(m-1, result)
if (!st.empty() && st.top().second == -1) {
auto top = st.top(); // 取出栈顶的 pair
int prev_m = top.first; // 获取 pair 的第一个元素
int second_val = top.second; // 获取 pair 的第二个元素
st.pop();
st.push({prev_m, result}); // 将 result 替换第二个值并推入栈
}
}
return result;
}
int main() {
int m = 2, n = 1;
std::cout << "Ackermann(" << m << ", " << n << ") = " << ackermann(m, n) << std::endl;
return 0;
}
