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;

}