C语言-数据结构-递归

一.简介

在哔哩哔哩看视频学的,赫斌老师数据结构入门的内容-b站搜索:av6159200(P50-P58),因为我在早期学c语言的时候就学过的递归,那时一直理解不了汉诺塔,最后花了很长时间才彻底搞懂,在看到学到这个数据结构有递归的时候,自己就重新写了一下汉诺塔递归的实现,不过通过了视频了解了大致递归的一下原理把.

---

二.什么是递归

递归其实说得简单点,大概就是自己调用自己,或者调用别的函数,并且递归要有结束条件,就是当条件是什么的时候,就结束调用,

简单的举例:

                        累加:1+2+3+4,为了简单的理解就不加到100了

                            利用递归的话,我们就可以用4进去一直来减1,然后当减到为1的时候结束调用.

int add(n)

{

            if(n==1)                    //为1的时候结束调用

              {

                        return 1;

                }

                else

                    {

                            return = n+ add(n-1);                    //一直调用自己

                    }

}

n = 4时 即 return = 4 + add(3)

n = 3时 即 return = 3 + add(2)

n = 2 时 即 return = 2 + add(1)

然后我们又知道n为1 时 返回的是1

所以反向推就可以知道 add(2) = 2 + 1

add(3) = 3 + 2 + 1

add(4) = 4 + 3 + 2 +1

这其实类似于栈的原理-先进后出,就是每次要用最后一个来推出上面的那一个.

---

三.递归实现汉诺塔的图解

汉诺塔的来历,相信很多人都知道了,这里就不多说了.

1 2 3 4 5 6

---

四.汉诺塔源码(可复现)

# include <stdio.h>

void hanoi(char , char , char, int);    //函数声明

int main(void)

{

    int val;

    printf("请输入你要移动几个盘子\n");

    printf("盘子 = ");

    scanf("%d", &val);

    hanoi('A' , 'B' , 'C', val);

    return 0;

}

/* 汉诺塔 */

void hanoi(char A, char B, char C, int val)

{

            if(1 == val)

            {

                    printf("%c->%c\n", A, C);

                }

                else

                {

                    hanoi(A, C, B, val-1);

                    printf("%c->%c\n", A, C);

                    hanoi(B, A, C, val-1);

                    }

}

---

五.递归的应用

    树和森林就是以递归的方式定义的

    树和图的很多算法都是以递归来实现的

    很多数学公式就是以递归的方式定义的(如:斐波拉契序列)

---

六.循环和递归

递归:

            易于理解

            速度慢

              所用存储空间大

循环:

                不易理解

                  速度快

                  所用存储空间小