Definition

Recursion

the process of repeating a function, each time applying it to the result of the previous stage.

​

  • 经过树形结构，和嵌套结构后的思想：可像数学函数一样，一个个嵌套，完美解决递归
演示递归 debug
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* recur.c -- recursion illustration */
#include <stdio.h>
void up_and_down(int);

int main(void)
{
    up_and_down(1);
    return 0;
}

void up_and_down(int n)
{
    printf("Level %d: n location %p\n", n, &n); // 1
    if (n < 4)
        up_and_down(n+1);
    printf("LEVEL %d: n location %p\n", n, &n); // 2
}

output

1
2
3
4
5
6
7
8
Level 1: n location 000000000061FE00
Level 2: n location 000000000061FDD0
Level 3: n location 000000000061FDA0
Level 4: n location 000000000061FD70
LEVEL 4: n location 000000000061FD70
LEVEL 3: n location 000000000061FDA0
LEVEL 2: n location 000000000061FDD0
LEVEL 1: n location 000000000061FE00

递归工作栈

从上述可以看出，函数调用属于后调用先返回的过程。那么，符合栈的性质。所以，每当调用一个函数，系统就为这个函数在栈顶中分配空间，但函数返回就出栈，释放空间。存储区里包括：所有实参，局部变量，返回值。

函数思想解决简单递归

  1. G(10)
  2. G(9) + 10
  3. G(8) + 9 + 10
    ….
  • 思想可以联系树的递归遍历作图，将前后节点（函数）合并得到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
int GrowWordNumber(int d)
{
    if(d == 1)
        return 1;
    else
    {
        return GrowWordNumber(d - 1) + d;
    }
    
}

int main()
{
    int num = GrowWordNumber(10);
    printf("%d\n", num);
    return 0;
}

递归和循环

  • 每次递归都会创建一组变量 （函数的参数），所以占用的内存会更多，而且数量有限，因为这些参数存放在栈区

  • 尾递归
    即递归函数中被调函数是最后一条语句，所以根据递归的思想，它相当于循环。如果不是尾递归，则不能用简单的循环实现

递归和倒序输出

  • 这种情况就体现到递归的好处
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
/* binary.c -- prints integer in binary form */
#include <stdio.h>
void to_binary(unsigned long n);

int main(void)
{
    unsigned long number;
    printf("Enter an integer (q to quit):\n");
    while (scanf("%lu", &number) == 1)
    {
        printf("Binary equivalent: ");
        to_binary(number);
        putchar('\n');
        printf("Enter an integer (q to quit):\n");
    }
    printf("Done.\n");
    
    return 0;
}

void to_binary(unsigned long n)   /* recursive function */
{
    int r;
    
    r = n % 2;  //看成二进制，取最后一位数
    if (n >= 2)
        to_binary(n / 2);//看成二进制，小数点前移
     putchar(r == 0 ? '0' : '1');
    
    return;
}
hanoi汉诺塔
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
void hanoi(int n, char one, char two, char three)
{
    if(n == 1)
        printf("%c -> %c\n", one, three);
    else
    {
        hanoi(n-1, one, three, two);//（排除最后一个）直到只剩下一个的时候，移动
        printf("%c --> %c\n", one, three);//移动最后一个
        hanoi(n-1, two, one, three);
        printf("\n");
    }
    
}
int main()
{
    int n = 3;
    hanoi(n, 'A', 'B', 'C');

    return 0;
}