递归的学习与应用-创新互联
- 前言
- 一、递归的定义
- 二、递归的演示
- 三、递归的基本原理
- 特点1
- 特点2
- 特点3
- 特点4
- 特点5
- 四、尾递归
- 例题1
- 思考
- 例题2
- 思考
- 例题3
- 五、递归的优缺点
- 优点
- 缺点
- 总结
前言
笔者本周粗略学习了递归，现以一下博客记录自习学习的过程，如果错误，请不吝指出。
一、递归的定义c允许函数调用他自己，这种调用过程称为递归。递归有时难以捉摸，有时却很方便使用。结束递归是递归的难点.，因为如果递归代码中没有终止递归的条件测试部分，一个调用自己的函数会无限递归
二、递归的演示# includevoid digui(int);
int main()
{digui(1);
return 0;
}
void digui(int n)
{printf("%d , %p\n", n, &n);//#1语句
if(n<4)
digui(n+1);
printf("%d , %p\n", n, &n);//#2语句
} 输出结果
1 , 000000000062FE00
2 , 000000000062FDD0
3 , 000000000062FDA0
4 , 000000000062FD70
4 , 000000000062FD70
3 , 000000000062FDA0
2 , 000000000062FDD0
1 , 000000000062FE00我们通过以上程序分析递归的运行方式。
首先，main函数调用了带参数1的digui（）函数，所以第一步先执行带参数1的递归函数中的#1语句，当程序继续向下执行时，遇到了我们的递归函数，此时的递归函数中的参数是n+1，也就是2，那么重新开始一次新的digui（）函数，只不过此时的参数是2，然后继续打印参数为2的#1语句。
当递归函数调用到参数为4时，我们的digui（）函数便再调用自己，那么便打印#2语句。接着将控制权返回上一层digui（）函数，也就是digui（3）
因为digui（3）在刚开始并未执行#2语句，而是先被自己调用进入了新的函数，当递归结束时他的执行步骤的位置将会返回digui（3）后的下一步，也就是执行#2语句。
因此我们可以得出一条简单的函数调用链：digui(1)->digui(2)->digui(3)->digui(4)，当digui(4)结束后，将控制权返回digui(3)，那么有digui(4)->digui(3)->digui(2)->digui(1)
三、递归的基本原理因为笔者的总结能力浅薄，所以也许看到上述文字你并不能很理解
接下来笔者将会给出递归的几个原理帮助你的理解、
每级函数都有自己的变量，也就是说，第一次函数调用的digui（n+1）与第二次函数调用的digui（n+1）不同，最终当程序返回digui（）的第一级调用时，最初的n仍是他的初值1
特点2每次函数调用都会返回一次，当函数执行完毕后，控制权将会被传回上一级递归。程序必须按顺序逐级返回递归，不能跳级。
特点3递归函数中位于递归调用之前的语句，也就是我们上面的#1语句，均按照被调函数的顺序执行。
特点4递归函数中位于递归调用之后的语句，也就是我们上面的#2语句，均按照被调函数相反的顺序执行。
特点5递归函数必须包含能让递归调用停止的语句。
通常，递归函数用if或其他等价的测试条件等于某特定的值时停止调用。
笔者将会在下文给出例题以解释。
最简单的递归形式就是把递归调用放置于函数的末尾，即正好在return的语句之前
尾递归时最简单但的递归形式，因为他相当于循环。
我们以几道例题深入了解递归
以下是使用递归计算阶乘的代码
# includeint jiecheng (int n)
{int ans;
if(n>0)//通常用if语句进行终止
ans = jiecheng(n-1)*n;
else
ans = 1;//最需要我们注意的时递归的终止条件
return ans;
}
int main()
{int i;
scanf("%d", &i);
printf("%d", jiecheng(i));
return 0;
} 可以使用循环与递归计算阶乘，那么使用哪一个好？
一般，选择循环比较好，首先，每次递归都会创建一组变量，所以递归使用的内存更多，而且每次递归都会把创建的一组新变量放在栈中，递归调用的数量受限于内存空间
以下是用递归将十进制转换为二进制
当函数执行完毕，从最后一层递归函数开始putchar二进制数，最后一层函数的putchar是二进制数的第一位
若不知道为何从最后一步开始返回，可以思考上方的特点4
# includevoid digui(int n)
{int r;
r = n % 2;//十进制的第一次取模是二进制的最后一位
if (n >= 2)
digui(n / 2);//每次使n变化
putchar(r == 0 ? '0' : '1');
return;
}
int main()
{int n;
while (scanf_s("%d", &n)==1)//scanf返回值为如果成功，该函数返回成功匹配和赋值的个数。如果到达文件末尾或发生读错误，则返回 EOF。
{digui(n);
printf("输入q终止");
putchar('\n');
}
return 0;
} 一般而言，对于数字n，其二进制的最后一位是n%2，因此，计算的第一位数字正好是待输出二进制的最后一位，这一规律提醒我们，在递归函数之前计算n%2，在递归之后打印计算结果。且要获得下一位数字，必须把原数除2，这种计算方法相当于在十进制下把小数点左移一位。且通过putchar(r == 0 ? ‘0’ : ‘1’);将数值转换成字符
例题3以下是用递归合并两个有序链表
合并两个有序链表
# include# includetypedef struct Node
{int data;
struct Node* pNext;
}NODE, *PNODE;
PNODE CreateList()
{PNODE pHead = (PNODE)malloc(sizeof(NODE));//链表不用预先设定长度
PNODE pTail = pHead;
int val;
int len;
printf("请输入链表的长度");
scanf_s("%d", &len);
for (int i = 0; i< len; ++i)
{PNODE pNew = (PNODE)malloc(sizeof(NODE));
printf("请输入第%d个节点的值", i + 1);
scanf_s("%d", &val);
pNew->data = val;
pTail->pNext = pNew;
pTail = pNew;
pTail->pNext = NULL;//初始化节点的指针域
}
return pHead;
}
PNODE MergeTwoList(PNODE p1, PNODE p2)
{if (p1 == NULL)//谁先为空便是递归的结束条件
return p2;//返回p2的原因是使让最底层递归结束后将p2返回对上一层的p1->next赋值
if (p2 == NULL)
return p1;//返回p1的原因是使让最底层递归结束后将p1返回对上一层的p2->next赋值
if (p1->data< p2->data)
{p1->pNext = MergeTwoList(p1->pNext, p2);//谁小便移动谁，谁移动便返回谁以便于上一级节点连接
return p1;
}
else
{p2->pNext = MergeTwoList(p1, p2->pNext);
return p2;
}
}
void bianli(PNODE pHead)
{PNODE p = pHead->pNext;
while (p)
{printf("%d ", p->data);
p = p->pNext;
}
}
int main(void)
{ PNODE Head_1 = CreateList();
PNODE Head_2 = CreateList();
MergeTwoList(Head_1,Head_2);//也可以设立两个新的指针指向头结点
bianli(Head_1);
return 0;
} 同时我们需要注意例如p1->pNext = MergeTwoList(p1->pNext, p2);,我们是先对递归函数仅需调用再赋值，也就是说，当调用未结束时，p1->nexr一直未曾赋值，但虽然一直未赋值，但是像l1->next与l2->next一直在变化，所以递归结束后返回的是变化后的节点
递归结束后返回上一层断点处执行程序，未赋值的就先赋值
赋值后笔者还不知如何打印证明，但原理是这样的
递归返回的值是新赋值的值
五、递归的优缺点 优点为某些编程问题提供了简单的解决方案
缺点会快速消耗计算机中的内存
总结尽管初步了解了阶乘的使用，但是在平时做题可能一般想不到使用其方法，还是需要多做题巩固知识，下周的学习计划便以刷题为主，逐步巩固自己前面的知识
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章标题：递归的学习与应用-创新互联
文章起源：http://pwwzsj.com/article/djcscj.html
