数据结构----递归

1.使用递归实现阶乘

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

2.用递归求和(普通实现方式)

int sum(int n){
    if(1 == n){
        return 1;
    }else{
        return n + sum(n-1);
    }
}

3.另一种递归求和实现

//使用三目运算符
int sum(int n){
    return n>0? n + sum(n-1) : 0;
}
//不使用三目运算符
int sum(int n){
    int result=0;
    (n>0)&&(result=sum(n-1)+n);
    return result;
}

4.循环和递归的优缺点

使用递归能实现的,使用循环通常都能够实现

• 递归
  • 容易理解
  • 速度慢
  • 浪费空间
• 循环
  • 不易理解
  • 速度快
  • 节省空间

5.使用递归实现汉罗塔

• 汉罗塔问题描述:

  • 将A柱子上的 n 个盘子借助 B 柱子 移动到 C

• 伪算法:

  • A柱子上只有1个盘子

    • 直接从 A 移动到 C

  • 否则

    • 只需要将A柱子上的 n-1 个盘子借助C移动到B

    • 将A柱子上的第 n 个盘子直接移动到C

    • 将B柱子上的 n-1 个盘子借助A移动到C

• 代码实现

#include <stdio.h>
#include <stdlib.h>

void hanluota(int n,char A,char B,char C){
    if (1==n)
    {
        printf("***将第%d个盘子从%c柱子移动到%c柱子***\n", n,A,C);
    }else{
        //将A柱子上的 n-1 个盘子借助C移动到B
        hanluota(n-1,A,C,B);
        //将A柱子上剩下的第 n 个盘子直接移动到C
        printf("---将第%d个盘子从%c柱子移动到%c柱子---\n", n,A,C);
        //将B柱子上的 n-1 个盘子借助A移动到C
        hanluota(n-1,B,A,C);
    }
}

int main(){
    hanluota(3,'A','B','C');
    return 0;
}

• 运行结果

M:\数据结构与算法>test
***将第1个盘子从A柱子移动到C柱子***
---将第2个盘子从A柱子移动到B柱子---
***将第1个盘子从C柱子移动到B柱子***
---将第3个盘子从A柱子移动到C柱子---
***将第1个盘子从B柱子移动到A柱子***
---将第2个盘子从B柱子移动到C柱子---
***将第1个盘子从A柱子移动到C柱子***