# GESP等级：四级 | GESP Python 四级考点
"""
第4节 递归初探
==============
面向7-10岁少儿 —— 用turtle画分形树可视化递归

知识点：
  - 递归：函数调用自己
  - 两个关键：终止条件 + 递归调用
  - 阶乘：n! = n * (n-1)!
  - 分形树：递归可视化
  - 递归执行过程：递去 → 触底 → 归来
"""

import turtle
import time
import sys

# 设置递归深度限制（防止讲课过程中意外崩溃）
sys.setrecursionlimit(1000)


# ============================================================
# 第一部分：递归基础 —— 阶乘
# ============================================================

def factorial(n, indent=0):
    """递归计算阶乘，带缩进显示执行过程"""
    prefix = "  " * indent
    print(f"{prefix}→ 进入 factorial({n})")

    if n == 1:
        print(f"{prefix}  → 触底！factorial(1) = 1")
        print(f"{prefix}← 返回 1")
        return 1

    result = n * factorial(n - 1, indent + 1)
    print(f"{prefix}← 返回 {n} × {n-1}! = {result}")
    return result


def demo_factorial():
    """演示阶乘递归的执行过程"""
    print("=" * 50)
    print("【递归演示】阶乘 factorial(5)")
    print("=" * 50)
    print("递去（拆解）→ 触底 → 归来（回溯）")
    print("-" * 50)
    result = factorial(5)
    print("-" * 50)
    print(f"最终结果：5! = {result}")
    print()
    print("用循环验证：", end="")
    loop_result = 1
    for i in range(1, 6):
        loop_result *= i
    print(f"5! = {loop_result}")
    print("两种方法结果一样！")


# ============================================================
# 第二部分：递归求和
# ============================================================

def sum_recursive(n):
    """递归求和 sum(n) = n + sum(n-1), sum(1) = 1"""
    if n == 1:
        return 1
    return n + sum_recursive(n - 1)


def demo_sum_recursive():
    """演示递归求和"""
    print("\n" + "=" * 50)
    print("【递归求和】1+2+3+...+n")
    print("=" * 50)

    n = 10
    result = sum_recursive(n)
    print(f"1+2+...+{n} = {result}")
    print(f"用公式验证：{n}×({n}+1)/2 = {n * (n + 1) // 2}")
    print()

    # 显示执行过程
    print("拆解过程：")
    print(f"  sum({n}) = {n} + sum({n-1})")
    print(f"  sum({n-1}) = {n-1} + sum({n-2})")
    print(f"  ...")
    print(f"  sum(2) = 2 + sum(1)")
    print(f"  sum(1) = 1 （← 触底！）")
    print(f"  sum(2) = 2 + 1 = 3")
    print(f"  sum(3) = 3 + 3 = 6")
    print(f"  ...")
    print(f"  sum({n}) = {n} + {result - n} = {result}")


# ============================================================
# 第三部分：斐波那契数列
# ============================================================

def fib(n):
    """递归计算斐波那契数列"""
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)


def demo_fibonacci():
    """演示斐波那契数列"""
    print("\n" + "=" * 50)
    print("【斐波那契数列】fib(n) = fib(n-1) + fib(n-2)")
    print("=" * 50)

    n = 10
    print(f"斐波那契数列前{n}项：")
    for i in range(1, n + 1):
        print(f"  fib({i}) = {fib(i)}")
    print()
    print("规律：每个数等于前两个数之和")
    print("  fib(5) = fib(4) + fib(3)")
    print("  fib(4) = fib(3) + fib(2)")
    print("  fib(3) = fib(2) + fib(1) = 1 + 1 = 2")
    print("  fib(2) = 1")
    print("  fib(1) = 1")


# ============================================================
# 第四部分：递归执行过程可视化（用缩进树）
# ============================================================

def recursion_tree(n, depth=0):
    """用树形结构显示递归执行过程"""
    prefix = "  " * depth + "├── "
    child_prefix = "  " * depth + "│   "

    print(f"{prefix}f({n})")

    if n <= 1:
        print(f"{child_prefix}→ 返回 1")
        return 1

    # 左分支
    print(f"{child_prefix}左：")
    left = recursion_tree(n - 1, depth + 1)

    # 右分支
    print(f"{child_prefix}右：")
    right = recursion_tree(n - 2, depth + 1)

    result = left + right
    print(f"{child_prefix}→ f({n}) = {left} + {right} = {result}")
    return result


def demo_recursion_tree():
    """树形递归可视化"""
    print("\n" + "=" * 50)
    print("【递归树】斐波那契数列调用过程")
    print("=" * 50)
    print(f"fib(5) 的递归调用树：")
    print()
    recursion_tree(5)


# ============================================================
# 第五部分：turtle分形树 —— 递归可视化经典
# ============================================================

def setup_screen():
    """设置画布"""
    screen = turtle.Screen()
    screen.title("递归分形树 —— 用turtle画递归")
    screen.bgcolor("white")
    screen.setup(800, 600)
    screen.tracer(0)  # 加速
    return screen


def draw_fractal_tree(t, x, y, length, angle, depth):
    """画分形树 —— 递归"""
    if depth == 0:
        return

    # 移动到起始位置
    t.penup()
    t.goto(x, y)
    t.pendown()
    t.setheading(90)  # 朝上

    # 画树干
    t.forward(length)

    # 记录当前顶端位置
    end_x = t.xcor()
    end_y = t.ycor()

    # 左分支
    t.left(angle)
    draw_fractal_tree(t, end_x, end_y, length * 0.7, angle, depth - 1)

    # 右分支
    t.right(angle * 2)
    draw_fractal_tree(t, end_x, end_y, length * 0.7, angle, depth - 1)

    # 恢复角度
    t.left(angle)


def turtle_fractal_tree():
    """用turtle画递归分形树"""
    screen = setup_screen()
    t = turtle.Turtle()
    t.speed(0)
    t.color("brown")
    t.pensize(2)
    t.hideturtle()

    # 显示标题
    title_t = turtle.Turtle()
    title_t.hideturtle()
    title_t.penup()
    title_t.goto(0, 260)
    title_t.color("darkgreen")
    title_t.write("递归分形树 —— 一个函数画出整棵树！",
                  align="center", font=("SimHei", 20, "bold"))

    # 显示递归规则
    rule_t = turtle.Turtle()
    rule_t.hideturtle()
    rule_t.penup()
    rule_t.goto(0, 230)
    rule_t.color("gray")
    rule_t.write("规则：树干→分两枝→每枝再分→长度变短→直到终止",
                 align="center", font=("SimHei", 12, "normal"))

    # 画树
    draw_fractal_tree(t, 0, -250, 120, 30, 8)

    # 更新画面
    screen.update()

    # 总结
    summary_t = turtle.Turtle()
    summary_t.hideturtle()
    summary_t.penup()
    summary_t.goto(0, -280)
    summary_t.color("purple")
    summary_t.write("递归的奥秘：简单规则 × 自己调用自己 = 复杂图案",
                    align="center", font=("SimHei", 16, "bold"))

    screen.mainloop()


# ============================================================
# 第六部分：turtle递归画正方形嵌套
# ============================================================

def draw_squares(t, size):
    """递归画正方形嵌套"""
    if size < 20:
        return

    # 画正方形
    for _ in range(4):
        t.forward(size)
        t.left(90)

    # 移动到内部位置
    t.penup()
    t.forward(15)
    t.left(90)
    t.forward(15)
    t.right(90)
    t.pendown()

    # 递归画更小的
    draw_squares(t, size - 30)


def turtle_nested_squares():
    """用turtle画嵌套正方形"""
    screen = turtle.Screen()
    screen.title("递归嵌套正方形")
    screen.bgcolor("lightyellow")
    screen.setup(600, 600)

    t = turtle.Turtle()
    t.speed(3)
    t.color("blue")
    t.pensize(2)

    # 移动到合适位置
    t.penup()
    t.goto(-150, 150)
    t.pendown()

    draw_squares(t, 300)

    # 显示信息
    t.penup()
    t.goto(0, -250)
    t.color("darkblue")
    t.write("递归正方形：大→中→小→更小...",
            align="center", font=("SimHei", 14, "bold"))

    t.hideturtle()
    screen.mainloop()


# ============================================================
# 第七部分：递归计数 —— 数递归调用了多少次
# ============================================================

call_count = 0


def count_recursive(n):
    """计数递归调用次数"""
    global call_count
    call_count += 1

    if n == 1:
        return 1
    return n + count_recursive(n - 1)


def demo_call_count():
    """演示递归调用次数"""
    print("\n" + "=" * 50)
    print("【递归计数】递归函数调用了多少次？")
    print("=" * 50)

    global call_count

    for n in [5, 10, 20, 50]:
        call_count = 0
        result = count_recursive(n)
        print(f"  sum({n}) = {result}，递归调用了 {call_count} 次")

    print()
    print("规律：递归 n，调用 n 次")


# ============================================================
# 第八部分：递归 vs 循环 性能对比
# ============================================================

import time


def demo_vs_loop():
    """递归 vs 循环性能对比"""
    print("\n" + "=" * 50)
    print("【递归 vs 循环】性能对比")
    print("=" * 50)

    n = 30

    # 循环计算斐波那契
    start = time.time()
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    loop_time = time.time() - start

    # 递归计算
    start = time.time()
    fib_result = fib(n)
    recursive_time = time.time() - start

    print(f"fib({n}) = {a}")
    print(f"  循环用时：{loop_time:.6f}秒")
    print(f"  递归用时：{recursive_time:.6f}秒")
    print(f"  递归比循环慢了约 {recursive_time / max(loop_time, 0.000001):.0f} 倍")
    print()
    print("结论：递归代码更简洁，但循环性能更好")
    print("选择哪种？看情况！")


# ============================================================
# 第九部分：互动 —— 递归猜谜
# ============================================================

def recursion_quiz():
    """递归小问答"""
    print("\n" + "=" * 50)
    print("【递归小测验】看看你理解了没有")
    print("=" * 50)

    questions = [
        {
            "q": "递归是指函数___",
            "options": ["A. 调用另一个函数", "B. 调用自己", "C. 被其他函数调用"],
            "answer": "B"
        },
        {
            "q": "递归的两个关键是___",
            "options": ["A. 循环和判断", "B. 终止条件和递归调用", "C. 输入和输出"],
            "answer": "B"
        },
        {
            "q": "如果递归没有终止条件会怎样？",
            "options": ["A. 正常运行", "B. 运行一次就停", "C. 无限递归导致崩溃"],
            "answer": "C"
        },
        {
            "q": "阶乘 5! 等于多少？",
            "options": ["A. 60", "B. 120", "C. 25"],
            "answer": "B"
        }
    ]

    score = 0
    for i, q in enumerate(questions, 1):
        print(f"\n第{i}题：{q['q']}")
        for opt in q['options']:
            print(f"  {opt}")
        answer = input("请输入答案（A/B/C）：").strip().upper()
        if answer == q['answer']:
            print("正确！")
            score += 1
        else:
            print(f"不对哦，正确答案是 {q['answer']}")

    print(f"\n你答对了 {score}/{len(questions)} 题！")
    if score == 4:
        print("太棒了！你已经理解递归了！")
    elif score >= 2:
        print("不错，再复习一下就更好了！")
    else:
        print("别急，再来看看教案吧！")


# ============================================================
# 第十部分：主程序
# ============================================================

def main():
    print("""
    ╔══════════════════════════════════╗
    ║    递归初探学习程序                ║
    ╚══════════════════════════════════╝
    """)

    while True:
        print("\n请选择要运行的功能：")
        print("1. 递归阶乘（带执行过程）")
        print("2. 递归求和演示")
        print("3. 斐波那契数列")
        print("4. 递归树可视化")
        print("5. 递归调用次数统计")
        print("6. 递归 vs 循环 对比")
        print("7. turtle分形树（图形界面）")
        print("8. turtle嵌套正方形（图形界面）")
        print("9. 递归小测验")
        print("10. 全部运行")
        print("0. 退出")

        choice = input("\n请输入数字（0-10）：").strip()

        if choice == "1":
            demo_factorial()
        elif choice == "2":
            demo_sum_recursive()
        elif choice == "3":
            demo_fibonacci()
        elif choice == "4":
            demo_recursion_tree()
        elif choice == "5":
            demo_call_count()
        elif choice == "6":
            demo_vs_loop()
        elif choice == "7":
            print("\n正在打开turtle图形窗口...")
            turtle_fractal_tree()
        elif choice == "8":
            print("\n正在打开turtle图形窗口...")
            turtle_nested_squares()
        elif choice == "9":
            recursion_quiz()
        elif choice == "10":
            demo_factorial()
            demo_sum_recursive()
            demo_fibonacci()
            demo_call_count()
            recursion_quiz()
        elif choice == "0":
            print("再见！记住递归口诀：")
            print("递归递归，自己调用自己！")
            print("终止条件+缩小范围 = 完美递归！")
            break
        else:
            print("输入有误，请重新选择。")


if __name__ == "__main__":
    main()