前言

递归是程序中很接近于数学语言的一种写法，使用递归编程在阅读代码易于理解，但是往往会带来效率低下的问题，效率问题暂且按下不表，本章主要讲讲对于递归的理解

提示：以下是本篇文章正文内容，下面案例可供参考

一、递归是什么？

百度解释：程序调用自身的编程技巧称为递归（ recursion）。在百度还有更细致的解释，我在这里就不多加赘述，我在这里谈谈自己的理解：可以理解在整个问题中有重叠的子问题，什么叫重叠子问题呢？即一个问题是不独立的，一个子问题在下一个阶段决策中可能会不停的用到。我在上面提到递归很接近数学语言，我就用数学公式公式举例：比如常用到的函数? f（n）=? f（n-1）+x；

那么f（n-1）就是f（n）的一个重叠子问题，它们有着相同的逻辑，只是参数由n变为n-1。

二、使用步骤

三要素

那么如何写一个递归的问题呢？经过无数前辈的不断总结，得到如下的三个要素：

第一要素：明确这个函数要干什么

第二要素：寻找递归结束条件

第三要素：找出函数的等价关系式

其实你可以简单理解记忆为哲学三问：我是谁（明确这个函数要干什么），我从哪里来（寻找递归结束条件），我要到哪里去（找出函数的等价关系式），在下面的解释过程中，我们以举例子的形式来描述这三个过程，一般会以比较简单的斐波那契数列来举例，但是我认为这个过于简单就像一个数学公式一样，你太轻易的理解公式，反而很难去真的理解递归的过程，所有我们以一个反转链表来举例，第一它的递归条件不是一个简单的数字变换，需要一定的理解第二我个人对于递归有个入门的理解，就来源于这个程序的编写。

2.1?明确这个函数要干什么

第一要素：明确这个函数要干什么

千万不要小看这一过程，就像你要做一件事情，你都没有准确的弄清楚你到底要干什么，那么你的结果很大概率上会失败，没有这个过程，你下面的程序将很难继续下去，同样在使用递归的过程中，你也要准确的定义这个函数到底要干什么，记住是准确定义，举个例子，数学中常用的

f（x），但是但是在不同的场合它所表达的意义也不同，比如在平面几何中，一般代表纵坐标，给定一个确定x，必然会有一个确定的纵坐标，这其实就是一个准确的定义，同样在实际问题，同样需要准确的定义：比如在反转链表中我可以定义：f（n）将有n个节点的链表反转，那么f（n-1）为将有n-1个节点的链表反转。

接下来定义函数

首先：我要建立一个函数它要去反转一个链表，同时返回反转后链表的头节点；

代码如下：

?
struct list{
    int id;
    struct list *next;
}

struct list *revelist(struct list *head)
{
    struct list *phead  //设为反转后的头指针

    //code...


    return phead;   
}


?

import numpy as np import pandas as pd import matplotlib.pyplot as plt import seaborn as sns import warnings warnings.filterwarnings('ignore') import ssl ssl._create_default_https_context = ssl._create_unverified_context

2.2寻找递归结束条件

第二要素：寻找递归结束条件

寻找递归的结束条件：这里引用一段对迭代过程进行控制的过程，同样适用于寻找递归的结束条件：“在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件”

递归的结束条件同样适用；

结束条件的作用是什么：举个通俗的例子，比如有这样一个故事：

从前有座山，山里有个庙，庙里有个老和尚，老和尚给小和尚讲故事，讲的是:

如果没有结束条件那么这个“故事”会无限的进行下去，但是程序在执行过程中内存是有限的，所以程序就会报错。

那么我们可以设定一个结束条件：比如，当小和尚睡着了（太烦了），老和尚就停止讲故事。

同样在递归中我们也加入一个调节用以结束递归过程，而且可以采用迭代过程控制的思想，那么反转链表过程中，我们无法确定递归的次数，那么我们仔细分析，发现当头节点所指向的下一个结点为NULL时递归结束,同时需要保护当传入参数时为NULL时直接返回

代码如下（示例）：

struct list{
    int id;
    struct list *next;
}

struct list *revelist(struct list *head)
{
    if(head==NULL||head->next==NULL)
    return head;

    struct list *phead  //设为反转后的头指针

    //code...


    return phead;   
}



data = pd.read_csv( 'https://labfile.oss.aliyuncs.com/courses/1283/adult.data.csv') print(data.head())

2.3找出函数的等价关系式

同样的我们可以借用迭代关系中的方法，“所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成”递归关系式也同样如此；

分析：如果我们要将有10个节点的链表反转，那么我们只需要将9个节点反转，再将第二个节点第一个节点反转；而想要将9个节点反转，只要将9个节点中剩余的8个节点反转，再将9个节点中的第一个节点和第二个节点反转即可；而要反转8个节点，只需要将剩余的7个节点反转，再将9个节点中的第一个节点和第二个节点反转即可；以此类推，直到结束调节；

因此，可以得到递推关系：

想要反转n个节点的链表，只需将剩余的n-1个节点反转，然后将第二个节点和第一个节点反转即可

struct list{
    int id;
    struct list *next;
}

struct list *revelist(struct list *head)
{
    if(head==NULL||head->next==NULL)
    return head;

    struct list *phead,curlist;  //设为反转后的头指针

    phead = revelist(head->next);
	curlist = head->next ;
	curlist->next = head ;
	head ->next = NULL;
    return phead;   
}

三、效率问题

以上就是一个动态规划三个要素的实现过程，开头我们说过，递归比较好理解但是很有可能会带来效率问题，因为我们会不断的计算重复重叠的子问题，具体我以后会开一篇文章新讲，这里我简单的提一下，我曾经遇到这样一道题，很多人应该也见过，这个问题叫做“盒中取球”，它的题目是这样的：今盒子里有n个小球，A、B两人轮流从盒中取球，每个人都可以看到另一个人取了多少个，
也可以看到盒中还剩下多少个，并且两人都很聪明，不会做出错误的判断。
我们约定：
每个人从盒子中取出的球的数目必须是：1，3，7或者8个。
轮到某一方取球时不能弃权！
A先取球，然后双方交替取球，直到取完。
被迫拿到最后一个球的一方为负方（输方）

实现函数当A赢时输出1，A输时输出0；这其实是一道动态规划的题，但是我用递归试了一下，当输出较大的数（初始球数）时，输出结果需要相当的时间，代码如下:有兴趣的同学可以输入60到80之间的数试试，

#include<stdio.h>
int f(int n)
{
	if(n==1)
	{
		return 0;
	}
	if(n==2)
	{
		return 1;
	}
	if(n==3)
	{
		return 0;
	}
	if(n==4)
	{
		return 1;
	}
	if(n==5)
	{
		return 0;
	}
	if(n==6)
	{
		return 1;
	}
	if(n==7)
	{
		return 0;
	}
	if(n==8)
	{
		return 1;
	}
	int c = !(f(n-1)&&f(n-3)&&f(n-7)&&f(n-8));
	return c;
}
int main()
{
	int n,c;
	while(scanf("%d",&n)!=EOF)
	{
		c = f(n);
		printf("%d\n",c);  
	}
}