P5461 赦免战俘

#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>
#include <cmath>
void pardon(auto & matrix,int x,int y,int size){if(size == 1) return;int half = size / 2;for(int i =x;i < x + half;i++ ){for(int j = y; j < y + half;j++){matrix[i][j] = 0;}}pardon(matrix,x + half,y,half);pardon(matrix,x,y + half,half);pardon(matrix,x + half,y + half,half);
}
int main(){int n;cin>>n;int m = pow(2,n);//vector<vector<int>> matrix (m,vector(m,1));auto matrix = vector(m,vector(m,1));pardon(matrix,0,0,m);for(auto & line :matrix){for(auto & x:line){cout<<x<<" ";}cout<<endl;}
}

有些递归函数返回一个值（例如斐波那契数列），而有些递归函数只有 return 语句，通常用于标识递归结束。让我们深入探讨这个问题。

递归函数的两种常见模式

递归返回值：
有些递归函数是用来计算和返回值的，比如斐波那契数列。每一次递归调用都会返回一个结果，这些结果会通过递归的方式汇聚起来，直到最终返回给调用者。

例如斐波那契数列的递归：
```
int fibonacci(int n) {if (n <= 1) return n;return fibonacci(n - 1) + fibonacci(n - 2);  // 返回计算的值
}
```
在这个例子中，每个递归调用都会计算一个值并将其返回。返回的结果被累加和传递，最终得到斐波那契数列的第 n 项。
递归没有返回值：
另一种常见的递归方式是通过递归完成某些任务（如修改全局/外部变量、打印输出等），但不返回值。这些递归通常通过 return 来控制递归的结束，而不关心返回的具体数值。

例如这个 releaseMomos 函数：
```
void releaseMomos(int x, int y, int size) {if (size == 1) return;  // 递归的终止条件releaseMomos(x, y, size / 2);  // 子递归// 完成当前任务后，返回父级递归
}
```
在这种情况下，递归的目的是分解问题或控制任务流，不需要返回具体的值。通过每次递归来修改状态或完成操作，然后在结束条件处通过 return 跳出递归。

为什么有些递归没有返回值？

当递归的目的是 执行操作（如修改数组、改变全局状态、打印等）而非 计算并返回值 时，我们并不需要在递归中返回任何数据。这类递归通过改变外部状态或执行操作来完成任务。典型的例子包括：

修改外部变量： 比如一个递归函数用于更新一个数组或矩阵的状态，每个递归调用修改某些元素，最终完成整个任务。
打印输出： 递归可以用于按特定顺序打印树或图结构，返回值没有意义，只是控制递归的流向。
树的遍历： 在树的遍历中，递归用于访问每个节点，执行操作（如修改节点值、计算路径和等），没有必要返回一个具体的值。

举例说明：

带返回值的递归（例如斐波那契数列）：

这种递归中，每个递归调用都计算并返回一个值，递归的结果会逐步传递到上一层。典型的计算任务，通过递归的返回值来组合最终的结果。
```
int fibonacci(int n) {if (n <= 1) return n;  // 基础情况return fibonacci(n - 1) + fibonacci(n - 2);  // 返回结果
}
```
不返回值的递归（例如矩阵分治）：

在这种递归中，返回值并不重要。递归更多的是“分解问题”，每层递归完成一个任务后返回给上一层，直到达到递归的终止条件。这类递归通过外部状态（如全局数组、输出等）来记录信息或进行操作。
```
void releaseMomos(int x, int y, int size) {if (size == 1) return;  // 递归结束条件releaseMomos(x, y, size / 2);  // 分解为更小的任务// 完成当前任务
}
```
这里递归本身没有返回值，只有 return 作为递归结束的标识。递归过程通过改变外部状态、打印信息等来完成任务。