递归与二叉树 - C语言实现

数据结构学习笔记 | 2026-05-14

---

第一部分：阶乘函数

一、基本概念

递归（Recursion） 是指函数在执行过程中调用自身的一种编程技巧。

• 递归的核心思想：将一个大规模问题分解为更小的同类子问题，直到问题规模小到可以直接解决
• 递归的两个必要条件：
  1. 终止条件（Base Case）：有一个明确的终止条件，防止无限递归
  2. 递归调用：每次递归调用都必须使问题规模缩小

二、算法思想

阶乘的定义：

• 当 ( n = 0 ) 时，( f(0) = 1 ) （终止条件）
• 当 ( n = 1 ) 时，( f(1) = 1 )
• 当 ( n > 1 ) 时，( f(n) = n \times f(n-1) ) （递归调用）

递归执行过程

以 fac(4) 为例：

fac(4) = 4 * fac(3)
       = 4 * 3 * fac(2)
       = 4 * 3 * 2 * fac(1)
       = 4 * 3 * 2 * 1
       = 24

三、函数实现

#include <stdio.h>

int fac(int n)
    {
        int f = 0;
        if ((n==0) || (n==1))
            {
                f = 1; // 递归必须得有一个明确的终止条件
            }
        else
            {
                f = n*fac(n-1); // 该函数处理的数据规模必须在递减
            }
        return f;
    }

代码解析

要素	说明
终止条件	`if ((n==0)
递归调用	f = n*fac(n-1) 将问题规模从 n 减小到 n-1
返回值	最终返回 1×2×3×…×n 的累积结果

关键点：递归必须有一个明确的终止条件，且每次递归调用必须使问题规模递减，否则会导致无限递归（栈溢出）。

四、使用示例

int main()
    {
        // 用递归的方法设计函数求上面公式的值
        int n = 4;
        int fa = fac(4); // 调用 fac(n)
        printf("%4d的阶乘为: %d\n",n,fa);
        return 0;
    }

运行结果：

4的阶乘为: 24

五、时间复杂度分析

参数	复杂度	说明
时间复杂度	O(n)	递归调用 n 次，每次 O(1)
空间复杂度	O(n)	递归调用栈深度为 n

六、关键知识点

1. 递归必须有两个条件：

   • 明确的终止条件
   • 递归调用使问题规模递减

2. 递归的代价：每次函数调用都有额外的栈空间开销，递归深度过大会导致栈溢出

3. 递归 vs 迭代：阶乘可以用循环（迭代）实现，通常迭代比递归更高效（省去函数调用开销）

七、完整代码

源代码文件：Factorial-from-Scratch-with-C.c

---

第二部分：斐波那契数列

一、基本概念

斐波那契数列（Fibonacci Sequence） 是一个经典的数列，每个数等于前两个数之和。

• 递推公式：( F(n) = F(n-1) + F(n-2) )
• 起始值：( F(1) = 1, F(2) = 1 ) （也有定义 ( F(0) = 0 )）
• 数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

二、算法思想

斐波那契数列的递归实现遵循递归的一般原则：

1. 终止条件：当 ( n < 2 ) 时，直接返回 n
2. 递归调用：( f(n) = f(n-1) + f(n-2) )

递归执行过程

以 fibonacci(5) 为例：

fibonacci(5)
  = fibonacci(4) + fibonacci(3)
  = (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
  = (fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0)) + (fibonacci(1) + fibonacci(0)) + 1
  = (1 + 1) + (1 + 0) + (1 + 0) + 1
  = 2 + 1 + 1 + 1 + 1
  = 5

三、函数实现

#include <stdio.h>

long fibonacci(int n)
    {
        int f = 0;
        if (n<2)
            {
                f = n;
            }
        else
            {
                f = fibonacci(n-1) + fibonacci(n-2);
            }
        return f;
    }

代码解析

要素	说明
终止条件	if (n<2) 当 n=0 或 n=1 时，返回 n 本身
递归调用	f = fibonacci(n-1) + fibonacci(n-2) 返回前两项之和
返回值类型	使用 long 类型以支持较大数值

注意：递归实现虽然简洁，但效率较低，存在大量重复计算（如上例中 fibonacci(2) 被计算了多次）。

四、使用示例

int main()
    {
        int n;
        printf("请输入一个正整数: ");
        scanf("%d",&n);
        if (n < 0)
            {
                printf("ERROR!\n");
                return 1;
            }
        long result = fibonacci(n);
        printf("F(%d) = %1d\n",n,result);
        return 0;
    }

运行结果：

请输入一个正整数: 5
F(5) = 5

斐波那契数列对照表：

n	0	1	2	3	4	5	6	7	8	9	10
F(n)	0	1	1	2	3	5	8	13	21	34	55

五、时间复杂度分析

参数	复杂度	说明
时间复杂度	O(2^n)	递归树中每个节点都展开为两个子节点，呈指数增长
空间复杂度	O(n)	递归调用栈的最大深度为 n

优化方向：使用记忆化递归或**动态规划（迭代）**可将时间复杂度优化到 O(n)。

六、关键知识点

1. 斐波那契数列的递推关系：每个数等于前两个数之和

2. 递归终止条件：当 n < 2 时直接返回 n（F(0)=0, F(1)=1）

3. 递归算法的问题：存在大量重复计算，时间复杂度呈指数级增长

4. 优化思路：

   • 记忆化递归：将计算过的值存储起来，避免重复计算
   • 迭代动态规划：从下往上计算，只需保留前两个值

七、完整代码

源代码文件：Fibonacci-from-Scratch-with-C.c

---

第三部分：二叉树

一、基本概念

二叉树（Binary Tree） 是每个节点最多有两个子树的树结构，通常称为左孩子和右孩子。

• 节点的组成：数据域 + 左指针 + 右指针
• 二叉树的特点：
  • 每个节点最多有两个子节点
  • 左子树和右子树有顺序之分
  • 即使只有一个子节点，也需要区分是左子树还是右子树

二叉树的分类

类型	特点
满二叉树	所有节点都有两个子节点，所有层都满
完全二叉树	最后一层可能不满，但节点从左到右连续
二叉搜索树	左子树所有节点小于根，右子树所有节点大于根

二、结构体定义

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

// 定义二叉树的节点的数据类型
typedef struct BTNode
    {
        int data; // 节点存储的数据（整型）
        struct BTNode *lchild; // 指向左孩子节点的指针
        struct BTNode *rchild; // 指向右孩子节点的指针
    } BiTNode; // 给结构体起别名 BiTNode

成员	含义
data	节点存储的数据（整型）
lchild	指向左孩子节点的指针
rchild	指向右孩子节点的指针

说明：typedef 为结构体定义了别名 BiTNode，简化后续代码的书写。

三、函数声明

int CreateBiTree(BiTNode **T);          // 创建二叉树
void PreOrderTraverse(BiTNode *T);     // 先序遍历

四、功能函数实现

1. 创建二叉树

// 创建二叉树
int CreateBiTree(BiTNode **T)
    {
        int ch;
        scanf ("%d",&ch);
        if (ch == -1) // 如果输入 -1，表示该位置没有节点（空节点）
            {
                *T = NULL; // 将当前节点指针置空
                return 0; // 返回空节点标记
            }
        else
            {
                *T = (BiTNode *)malloc(sizeof(BiTNode)); // 为新节点分配内存空间
                if (*T == NULL) // 判断内存分配是否成功（必须判断*T而不是T）
                    {
                        printf("内存分配失败!\n");
                        return 0;
                    }
                (*T)->data = ch; // 给新节点赋值
                printf("请输入%d的左孩子节点(-1表示无): ",ch);
                CreateBiTree(&((*T)->lchild)); // 递归创建上面创建节点的左子树
                printf("请输入%d的右孩子节点(-1表示无): ",ch);
                CreateBiTree(&((*T)->rchild)); // 递归创建上面创建节点的右子树
            }
    }

算法思想：

• 输入节点值，如果输入 -1 表示该位置为空
• 否则分配内存，创建新节点
• 递归创建左子树和右子树

2. 先序遍历

// 先序遍历二叉树
// 遍历规则：根节点 → 左节点 → 右节点
void PreOrderTraverse(BiTNode *T)
    {
        if (T == NULL) // 空节点直接返回
            {
                return;
            }
        printf("%d ",T->data);  // 先访问根节点
        PreOrderTraverse(T->lchild); // 递归遍历左节点
        PreOrderTraverse(T->rchild); // 递归遍历右节点
    }

先序遍历规则：根节点 → 左子树 → 右子树

五、使用示例

int main()
    {
        // 定义一个指向二叉树节点的指针变量
        BiTNode *T;
        printf("请输入二叉树的根节点: \n");
        CreateBiTree(&T);
        printf("前序遍历上面创建的二叉树: \n");
        PreOrderTraverse(T);
        printf("\n");
        return 0;
    }

示例输入输出

输入（构建如下二叉树）：

    1
   /
  2
 /
3

请输入二叉树的根节点:
1
请输入1的左孩子节点(-1表示无): 2
请输入2的左孩子节点(-1表示无): 3
请输入3的左孩子节点(-1表示无): -1
请输入3的右孩子节点(-1表示无): -1
请输入2的右孩子节点(-1表示无): -1
请输入1的右孩子节点(-1表示无): -1

输出：

前序遍历上面创建的二叉树:
1 2 3

六、图解

示例二叉树结构：

        1           ← 根节点
       / \
   NULL   2         ← 2是1的左孩子
          /
         3          ← 3是2的左孩子
        / \
      NULL NULL

先序遍历顺序：1 → 2 → 3
（先访问根，再遍历左子树，最后遍历右子树）

七、时间复杂度分析

操作	时间复杂度	说明
创建二叉树	O(n)	每个节点访问一次，n 为节点数
先序遍历	O(n)	每个节点访问一次

八、关键知识点

1. 二叉树节点的组成：数据域 + 左孩子指针 + 右孩子指针

2. 递归构建思想：构建每个节点时，递归地创建其左子树和右子树

3. 先序遍历的顺序：根节点 → 左子树 → 右子树（深度优先遍历的一种）

4. 内存管理：malloc 分配节点内存，free 释放（示例中未包含销毁函数）

5. 输入 -1 表示空节点：这是一种常用的二叉树构建约定

九、完整代码

源代码文件：Binary-Tree-from-Scratch-with-C.c