栈和递归

一、栈

1、概述

栈：一种满足一定约束的线性数据结构，只允许在栈顶插入push或删除pop元素。

这也体现了栈的另一个重要性质：先进后出。

用top来指示栈顶的位置。

2、构造

使用stack需要引入<stack>头文件、std命名空间

stack<T> s：定义了一个储存T类型数据的栈s。

#include "stack"
using namespace std;
int main() {
    stack<int> s;
    return 0;
}

3、使用

方法	功能	參数类型	返回值类型
push	压入元素到栈顶	T类型	无
pop	弹出栈顶元素	无	无
top	返回栈顶元素	无	T类型
empty	栈是否为空	无	bool类型 false 表示不为空，true 表示栈为空
size	栈的元素个数	无	非负整数（size_t类型）

/**
 * 栈的测试
 * @author  王铭颢
 * @Date  2022/11/23 15:26
 */

#include "iostream"
#include "stack"
using namespace std;

int main() {
    stack<int> s;
    s.push(123);
    s.push(234);
    s.push(345);

    while(!s.empty()) {
        cout << s.top() << endl;
        s.pop();
    }

    return 0;
}

二、递归

1、概述

递归：函数调用函数自身，一个函数在其定义中有直接或者间接调用自身都叫递归。而递归一般都用来解决有重复子问题的问题。

边界条件：递归的退出条件。

2、求阶乘

求阶乘：n! = n * (n - 1)!

int f(int n) {
    if(n == 1) return 1;
    else return n * f(n - 1);
}

3、斐波那契数列

斐波那契数列：F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2)

int fib(int n) {
    if(n == 1 || n == 2) return 1;
    else return f(n - 2) + f(n - 1);
}

4、汉诺塔

#include <stdio.h>

int count = 0;

void hanoi(int n, char x, char y, char z) {
    if (n == 1) {
        count++;
        printf("%3d : %c ---> %c\n", count, x, z);
    } else {
        hanoi(n - 1, x, z, y);              //将前 n-1 个盘子从x移动到y上
        count++;
        printf("%3d : %c ---> %c\n", count, x, z);  //将最底下的盘子从x移动到z
        hanoi(n - 1, y, x, z);              //将y上的 n-1 个盘子移动到z上
    }
}

int main(void) {
    int i;
    printf("请输入罗汉塔的层数：");
    scanf("%d", &i);

    hanoi(i, 'x', 'y', 'z');
    return 0;
}