递归特征方程,螺旋折线的递归算法

螺旋矩阵问题

问题描述：
螺旋矩阵是指一个呈螺旋状的矩阵，它的数字由第一行开始到右边不断变大，向下变大，向左变大，向上变大，如此循环。
创建n阶螺旋矩阵并输出。
输入描述：
输入包含多个测试用例，每个测试用例为一行，包含一个正整数n（1≤n≤50），用输入0表示结束。
输出描述：
每个测试用例输出n行，每行包含n个整数，整数之间用一个空格分隔。
样例
输入：
4
0
输出：
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7

问题分析：一个n阶的二维数组，从起始位开始向左、向下、向右、向上螺旋变大，输入n并输出这个二维数组，可以把问题由不同的增长方向分为四步，每完成一轮四步则规模减小2阶，起始数变为前面一轮的末尾加1，即问题变为解决为n的每一轮再加上规模为n-2的问题
算法设计：对规模为n的先按顺序向左、向下、向右、向上变大，最后再进行规模为n-2的增加，当最后为0的时候结束，若初始规模n为奇数，则最后规模为1的时候加上前一个值+1
代码实现：

void num(int a,int**n,int begin,int first){int i, j, k;if (a == 0){return;//已经赋值完}if (a == 1){//第一个为firstn[begin][begin] = first;return;}i = begin;j = begin;for (k = 0; k < a - 1; k++){//需要填写a-1个数,横向开始n[i][j] = first;first++;j++;}for (k = 0; k < a - 1; k++){//向下n[i][j] = first;first++;i++;}for (k = 0; k < a - 1; k++){//向左n[i][j]=first;first++;j--;}for (k = 0; k < a - 1; k++){//向上n[i][j] = first;first++;i--;}num(a - 2, n, ++begin, first);}

运行结果：

算法分析：采取递归的方法每一轮后将问题转换为规模更小的问题，每一轮分别由4步组成
而由于采取递归在时间上开销则相对更大
经验归纳：思考时可以试着把一个问题分为几步构成，采取递归可以将问题变为同类型规模更小的问题