前言

  1. 递归程序可被定义为“自我调用的程序”,但需要存在终止条件。
  2. 本篇文章准备通过 “递归” 算法和数据结构 “栈” ,来实现前缀、后缀、中缀表达式的计算和转换。
  3. 尾递归,可以解决当参数n过大时,栈溢出的情况,和迭代的速度相差不多。

N!mod M

  1. 书上有几道关于递归的题目觉得挺有意思,分享一下!
  2. 当N=10^3!、10^5!、10^6!, M=997就算N! mod M
  3. 一开始百思不得其解,因为这道题目要使用递归来写。这样N的数字那么大,肯定会溢出,于是了解了“尾递归”,解决了溢出问题。
  4. 另外又去了解了一个公式,大概就是辗转相除的变形吧。n (n-1) mod M == ((n mod m) ((n-1)mod M) mod M)
  5. 这道题目有点坑,大于996!都是997的倍数,所以都是0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #include <stdio.h>

    int handle(int n, int t){

    if(n == 1) return t;

    t *= n % 997;

    handle(n-1, t % 997);
    }
    int main(){
    int n, ans;

    scanf("%d", &n);
    ans = handle(n, 1);

    printf("%d", ans);
    return 0;
    }

前缀递归计算

  1. 思路是遇到操作符时,调用本身,知道遇到数字时开始返回
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    #include <stdio.h>
    int cnt;
    int prefix(char *s){
    int x = 0;

    while(s[cnt] == ' ') cnt++;

    if(s[cnt] == '+'){
    cnt++;
    return prefix(s) + prefix(s);
    }
    if(s[cnt] == '*'){
    cnt++;
    return prefix(s) * prefix(s);
    }
    if(s[cnt] == '-'){
    cnt++;
    return prefix(s) - prefix(s);
    }
    if(s[cnt] == '/'){
    cnt++;
    return prefix(s) / prefix(s);
    }
    while(s[cnt] >= '0' && s[cnt] <= '9'){
    x = 10 * x + s[cnt] - '0';
    cnt++;
    }

    return x;
    }
    int main(){
    char s[100];
    int ans;

    gets(s);
    ans = prefix(s);

    printf("%d", ans);
    return 0;
    }

img


后缀递归计算

  1. 一开始想模仿前面写后缀一样去写,去写一个不利用栈实现的程序,但还是没找到啥规律。
  2. 这个递归只是把for循环变成了调用自身
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    int cnt, num;
    int *stack;//数字栈
    char *op;//符号栈

    int pop(){
    return stack[--num];
    }
    void push(int n){
    stack[num++] = n;
    }
    int suffix(char *s){
    int t, x = 0;

    while(s[cnt] == ' ') cnt++;
    if(s[cnt] == '\0') return pop();

    if(s[cnt] == '+'){
    cnt++;
    push(pop() + pop());
    }
    if(s[cnt] == '-'){
    cnt++;
    t = pop(); //减法和除法弹出的顺序会影响到计算结果
    push(pop() - t);
    }
    if(s[cnt] == '*'){
    cnt++;
    push(pop() * pop());
    }
    if(s[cnt] == '/'){
    cnt++;
    t = pop();
    push(pop() / t);
    }
    while(s[cnt] >= '0' && s[cnt] <= '9'){
    x = 10 * x + s[cnt] - '0';
    cnt++;
    }
    if(x != 0) push(x);
    return suffix(s);
    }
    int main(){
    char s[100];
    int ans;

    gets(s);
    op = (char *)malloc(sizeof(char)*strlen(s));
    stack = (int *)malloc(sizeof(int)*strlen(s));

    ans = suffix(s);

    printf("%d", ans);
    return 0;
    }

留言

⬆︎TOP