栈的应用补充：

    迷宫问题

    二进制问题

    递归问题

    在传统的递归中，典型的模型是首先执行递归调用，然后获取递归调用的返回值并计算结果。以这种方式，在每次递归调用返回之前，您不会得到计算结果。传统地递归过程就是函数调用，涉及返回地址、函数参数、寄存器值等压栈（在x86-64上通常用寄存器保存函数参数），CTF-PWN的很多基础性漏洞EXP核心其实也是函数栈的问题。
    传统递归的缺点：

    • 效率低，占内存
    • 如果递归链过长（可以理解为对应的树的深度大），可能会statck overflow（栈溢出）

    尾递归，形式上函数尾部返回自身

    1. // 连乘操作的尾递归，不需要消栈
    2. int factorial(int n)
    3. {
    4.     return n == 0 ? 1 : n * factorial(n - 1);// 无需返回factorial(n)
    5. }
    1. //GCC开O1优化生成的汇编代码是通过函数调用，非尾递归的;
    2. factorial:
    3. .LFB22:
    4.     .cfi_startproc
    5.     pushq    %rbx // push the old n, means n + 1
    6.     .cfi_def_cfa_offset 16
    7.     .cfi_offset 3, -16 // maybe update the frame pointer?
    8.     movl    %edi, %ebx
    9.     movl    $1, %eax
    10.     testl    %edi, %edi // test if n == 0
    11.     je    .L2 // if is true, jumpt to .L2
    12.     leal    -1(%rbx), %edi // %edi = n - 1
    13.     call    factorial
    14.     imull    %ebx, %eax // result = n * factorial(n - 1)
    15. .L2:
    16.     popq    %rbx // pop the old n
    17.     .cfi_def_cfa_offset 8
    18.     ret
    19.     .cfi_endproc
    20. //O2优先级，则GCC会作尾递归优化：
    21. factorial:
    22. .LFB22:
    23.     .cfi_startproc
    24.     testl    %edi, %edi
    25.     movl    $1, %eax
    26.     je    .L2
    27.     .p2align 4,,10
    28.     .p2align 3
    29. .L3:
    30.     imull    %edi, %eax 
    31.     subl    $1, %edi
    32.     jne    .L3 // It's a loop
    33. .L2:
    34.     rep
    35.     ret
    36.     .cfi_endproc

    参考

    后缀表达式 & 符号匹配问题