1、递归调用：
递归调用就是在当前的函数中调用当前的函数并传给相应的参数，这是一个动作，这一动作是层层进行的，直到满足一般情况的的时候，才停止递归调用，开始从最后一个递归调用返回。

2、递归调用的方法计算4的阶乘为例代码如下：

/**
* 用递归算4的阶乘
*/
public class Factorial {
    public static void main(String[] args) {
       //对factorial方法进行调用 
       factorial(4);
    }
    //定义方法
    public static int factorial(int n) {
        if (n == 0) {
            System.out.println(n + "! = 0");
            return 1;
        } else {
            System.out.println(n);
            //用递归的方法进行阶乘处理
            int temp = n*factorial(n-1);
            System.out.println(n + "! = " + temp);
            return temp;
        }
    }
}
运行结果：
4
3
2
1
0! = 0
1! = 1
2! = 2
3! = 6
4! = 24

3、4的阶乘递归图解如下：

目录

前言

一、从阶乘引入

二、递归模板

1.递归函数模板

2.举例分析

三、从数学归纳法理解递归

四、更多递归实例

1.用递归方法编程计算Fibonacci数列

题目分析

程序

2.汉诺塔（Hanoi）问题

题目分析

程序

3.转置链表

题目分析

程序

总结

前言

如果一个对象部分地由它自己组成或按它自己定义，则我们称它是递归（Recursive）的。在日常生活中，字典就是一个递归问题的典型实例，字典中的任何一个词汇都是由“其他词汇”解释或定义的，但是“其他词汇”在被定义或解释时又会间接或直接地用到那些由它们定义的词。在数学中，数学归纳法也是递归的一种体现。

一、从阶乘引入

初学编程时，计算正整数n的阶乘是利用阶乘的定义即n!=n*(n-1)*(n-2)*...*2*1来计算的。代码如下：

#include <stdio.h>
int main(void)
{
    int i, n;
    long p = 1;
    printf("Please enter n:");
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        p = p * i;
        printf("%d! = %ld\n",i, p);
    }
    return 0;
}

其实，还可以将n!=n*(n-1)*(n-2)*...*2*1写成n!=n*(n-1)!，即利用(n-1)!来计算n!，同理再用(n-2)!来计算(n-1)!，即(n-1)!=(n-1)*(n-2)!，以此类推，直到用1!=1逆向递推出2!，再依次递推出3!，4!，...，n!时为止。这说明阶乘是可以根据其自身来定义的问题，因此阶乘也是可递归求解的典型实例。这个递归问题可用如下的公式来表示：

下面采用递归方法来实现阶乘的计算：

#include<stdio.h>
long Fact(int n);
int main(void)
{
    int n;
    long result;
    printf("Input n:");
    scanf("%d", &n);
    result = Fact(n);//调用递归函数Fact()计算n!
    if (result == -1)//处理非法数据
        printf("n < 0, data error!\n");
    else//输出n!值
        printf("%d! = %ld\n", n, result);
    return 0;
}
//函数功能：用递归法计算n!，当n >= 0时返回n!，否则返回-1
long Fact(int n)
{
    if (n < 0)//处理非法数据
        return -1;
    else if (n == 0 || n == 1)//基线情况，即递归终止条件
        return 1;
    else//一般情况
        return (n * Fact(n-1));//递归调用，利用(n-1)!计算n!
}

 可见，递归是一种可根据其自身来定义或求解问题的编程技术，它是通过将问题逐步分解为与原始问题类似的更小规模的子问题来解决问题的，即将一个复杂问题逐步简化并最终转化为一个最简单的问题，最简单的问题的解决，就意味着整个问题的解决。显然对于具体的问题首先需要关注的是：最简单的问题是什么？对于本例，n=0或1就是计算n!的最简单的问题。当函数递归调用到最简形式，即当n=1时，递归调用结束，然后逐级将函数返回值返回给上一级调用者。

二、递归模板

1.递归函数模板

一个递归函数必须包含如下两个部分：

（1）由其自身定义的与原始问题类似的更小规模的子问题，它使递归过程将持续进行，称为一般情况（General case）；

（2）递归调用的最简形式，它是一个能够用来结束递归调用过程的条件，通常称为基线情况（Base case）。

代码如下：

返回值类型 Recursive(类型 形式参数1， 类型 形式参数2，……)
{
    if (递归终止条件)//基本条件控制递归调用结束
        return 递归公式的初值;
    else//一般条件控制递归调用向基本条件转化
        return 递归函数调用返回的结果值;
}

像这种“在函数内直接或间接地调用自己”的函数调用，就称为递归调用（Recursive Call），这样的函数则称为递归函数（Recursive Function）。

2.举例分析

以第一目为例，基线情况是0!=1和1!=1；一般情况则是将n!表示成n乘以(n-1)!，如第一目代码中在调用函数Fact()计算n!的过程中又调用了函数Fact()来计算(n-1)!。例如要计算3!，需要经历如下步骤：

（1）在main函数中调用Fact(3)。

（2）为了计算3!，需要先调用函数Fact(3-1)计算2!。

（3）为了计算2!，需要先调用函数Fact(2-1)计算1!.

（4）计算1!时，递归终止，返回1作为1!的计算结果。

（5）返回到（3）中，利用1!=1，求出2!=2×1!=2×1=2，返回2作为2!的计算结果。

（6）返回到（2）中，利用2!=2，求出3!=3×2!=3×2=6。

（7）返回到main函数中，得出Fact(3)=6。

三、从数学归纳法理解递归

有关数学归纳法的原理，详见《人民教育出版社数学选择性必修第二册（A版）》第四章 数列 4.4*数学归纳法[2]。

下面给出数学归纳法的定义：

一般地，证明一个与正整数有关的命题，可按下列步骤进行：

（1）（归纳奠基）证明当时命题成立；

（2）（归纳递推）以“当时命题成立”为条件，推出“当时命题也成立”.

只要完成这两个步骤，就可以断定命题对从开始的所有正整数都成立，这种证明方法称为数学归纳法（mathematical induction）.

数学归纳法的核心就在于，只要我们能证明当n=1时等式成立（基线情况），且当n=k≥1时成立能够推出n=k+1时成立（一般情况），就能说明n≥1时成立。因为只要n=1成立，n=2就成立；n=2成立，n=3就成立；……；n=k成立，n=k+1就成立。

其实递归也蕴含了数学归纳法的思想：只要给出基线情况和一般情况的递推关系，就能得到基线情况以后的所有情况。因为知道了基线情况，通过递推关系就能得出基线情况后一级的情况；知道了基线情况后一级的情况，通过递推关系就能得出再后一级的情况……因此我们在编程时只需要关心：基线情况是什么，一般情况是什么。至于复杂的函数调用关系与返回关系，可以不用理会。

四、更多递归实例

1.用递归方法编程计算Fibonacci数列

题目分析

首先我们需要找出基线情况：fib(1)=fib(2)=1；然后找出一般情况：fib(n)=fib(n-1)+fib(n-2)(n>2)，即：

程序

#include<stdio.h>
long Fib(int n);
int main(void)
{
    int n, i, x;
    printf("Input n:");
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        x = Fib(i);//调用递归函数Fib()计算Fibonacci数列的第n项
        printf("Fib(%d) = %d\n", i, x);
    }
    return 0;
}
//函数功能：用递归法计算Fibonacci数列中的第n项的值
long Fib(int n)
{
    if (n == 1)
        return 1;//基线情况
    else if (n == 2)
        return 1;//基线情况
    else
        return (Fib(n-1)+Fib(n-2));//一般情况
}

2.汉诺塔（Hanoi）问题

如图，A杆上从下往上按大小顺序摞着n片黄金圆盘，规定每次只能移动一个圆盘，在小圆盘上不能放大圆盘，则把圆盘从下开始按大小顺序重新摆放到第二根上需移动多少次？

移动前：

移动后：

题目分析

首先我们需要找出基线情况：假设A杆上只有2个圆盘，即汉诺塔有2层，n=2，我们的移动步骤是先将1号圆盘从A移到C，再将2号圆盘从A移到B，最后将1号圆盘从C移到B。

移动前：

第一步：

第二步：

第三步：

然后找出一般情况：我们可以将n个圆盘分为两部分，“上面n-1个圆盘”看成一个整体，于是我们的移动步骤为先将n-1个圆盘从A移到C，再将n号圆盘从A移到B，最后将n-1个圆盘从C移到B。

而把n-1个圆盘从A移到C就相当于先将n-2个圆盘从A移到B，再将n-1号圆盘从A移到C，最后将n-2个圆盘从B移到C……一直到只剩下两个圆盘，即回到基线情况。

程序

首先我们需要设计一个函数Hanoi()，Hanoi(n, 'A', 'B', 'C')表示将n个圆盘借助于C由A移动到B；接着我们要设计一个函数Move()，调用Move(n, 'A', 'B')可输出一个语句：Move n: from 'A' to 'B'.

于是得到代码如下：

#include <stdio.h>
void Hanoi(int n, char a, char b, char c);
void Move(int n, char a, char b);
int main()
{
    int n;
    printf("Input the number of disks:");
    scanf("%d", &n);
    printf("Steps of moving %d disks from A to B by means of C:\n", n);
    Hanoi(n, 'A', 'B', 'C');/*调用递归函数Hanoi()将n个圆盘借助于C由A移动到B*/
    return 0;
}
/* 函数功能：用递归方法将n个圆盘借助c从a移到b */
void Hanoi(int n, char a, char b, char c)
{
    if (n == 2)
    {
        Move(n-1, a, c);
        Move(n, a, b);
        Move(n-1, c, b);
    }
    else
    {
        Hanoi(n-1, a, c, b);
        Move(n, a, b);
        Hanoi(n-1，c, b, a);
    }
}
/* 函数功能：将第n个圆盘从a移到b */
void Move(int n, char a, char b)
{
    printf("Move %d: from %c to %c\n", n, a, b);
}

这个程序只能实现n≥2的汉诺塔问题的求解。然而，进一步地，其实n=2也包含在n≥2的一般情况里，即可以把基线条件设成n=1，即A杆上只有一个圆盘，汉诺塔只有1层，移动操作便是将圆盘从A移到B。因此可以改写函数Hanoi()如下：

void Hanoi(int n, char a, char b, char c)
{
    if (n == 1)
    {
        Move(n, a, b);
    }
    else
    {
        Hanoi(n-1, a, c, b);
        Move(n, a, b);
        Hanoi(n-1，c, b, a);
    }
}

3.转置链表

定义函数，原型为struct link *Reverse(struct link *head);，功能为转置传入的链表顺序。函数不能返回一个新建的链表，必须通过改变原来的链表来实现功能，最后的返回值为转置后的链表的头节点的地址值。[3]

注意：不能通过简单地改变链表的数据域来转置链表；相反，需要改变链表的指针域。

链表节点的定义如下：

struct link
{
    int data;
    struct link *next;
};

题目分析

首先我们需要找出基线情况：当链表中只有2个节点时，我们只需新建一个结构体指针变量struct link* newhead;，让newhead指向第2个节点，然后让第2个节点的next指针指向第1个节点，最后让第1个节点的next指针指向NULL，最后返回newhead即可完成链表的转置。

接着我们需要找出一般情况：当链表中有n个节点（n>2）时，可把链表的后n-1个节点看成一个整体（先调用函数Reverse(head->next)使后n-1个节点的链表完成转置），这个整体与第1个节点组成一个2个节点的链表，再按照基线情况的操作，新建一个结构体指针变量struct link* newhead;，让newhead指向后n-1个节点组成的链表的头节点（这里为函数Reverse(head->next)的返回值），然后让head->next->next（第2个节点的next指针）指向头节点head，最后让头节点的next指针指向NULL，最后返回newhead即可完成链表的转置。

程序

struct link *Reverse(struct link *head)
{
    struct link *newhead = NULL;
    if (head->next->next == NULL)//基线情况：只有2个节点
    {
        newhead = head->next;
        head->next->next = head;//第2个节点的next指针
        head->next = NULL;//第1个节点的next指针
    }
    else//一般情况
    {
        newhead = Reverse(head->next);
        head->next->next = head;//当前节点的下一个节点的next指针
        head->next = NULL;//当前节点的next指针
    }
    return newhead;
}

这个程序只能完成n≥2个节点的链表的转置。然而，其实当n=2时，可以一并归入n≥2的情况中，于是我们可以把n=1甚至n=0作为基线条件（n=1即只有一个链表，n=0为空链表），修改后的程序如下：

struct link *Reverse(struct link *head)
{
    if (head == NULL || head->next == NULL)//基线情况：空链表或链表只有1个节点
    {
        return head;
    }
    else
    {
        struct link *newhead = Reverse(head->next);
        head->next->next = head;//当前节点的下一个节点的next指针
        head->next = NULL;//当前节点的next指针
        return newhead;
    }
}

总结

递归将复杂的情形逐次归结为较简单的情形来计算，一直到归并为最简单的情形为止，但任何递归函数都必须至少有一个基线情况，并且一般情况必须最终能转化为基线情况，否则程序将无限递归下去，导致程序出错。

在编写和阅读递归函数的代码时，我们只需注意两点：1.基线情况是什么？2.假设上一步已经做好了，当前这一步该怎么做？（一般情况的递推关系是什么？）倘若真的想要一行行debug代码，也要假定递归的次数较少，否则将进入无穷无尽的调用与返回之中，会导致程序非常的抽象难懂。

从上述的例子可以看出，用递归编写程序更直观、更清晰、可读性更好（若不深究函数之间复杂的调用与返回关系），更逼近数学公式的表示，更能自然地描述问题的逻辑，尤其适合非数值计算领域，如Hanoi塔、骑士游历、八皇后问题。但是从程序运行效率来看，递归函数在每次递归调用时都需要进行参数传递、现场保护等操作，增加了函数调用的时空开销，导致递归程序的时空效率偏低。

参考文献：

[1]苏小红 赵玲玲 孙志岗 王宇颖 等编著 蒋宗礼 主审，C语言程序设计（第4版），高等教育出版社，P109，P158-161.

[2]主编：章建跃 李增沪，副主编：李勇 李海东 李龙才，本册主编：李龙才 周远方，编写人员：李龙才 宋莉莉 张艳娇 周远方 桂思铭 郭慧清，责任编辑：张艳娇，美术编辑：王俊宏，数学选择性必修第二册（A版），人民教育出版社，P44-52

[3]原题为：Define reverse, which takes in a linked list and reverses the order of the links. The function may not return a new list; it must mutate the original list. Return a pointer to the head of the reversed list. You may not just simply exchange the first to reverse the list. On the contrary, you should make change on rest. 题目来源于Ricky_Daxia。

在调用一个函数的过程中又出现直接或间接的调用该函数本身，称为函数的递归调用。

直接：在调用函数f的过程中又要调用f函数。

间接：如果在调用f1函数的过程中要调用f2函数，而调用f2函数的过程中又要调用f1函数。

（简单来说在一个函数定义里面又使用了该函数，而一般用到递归调用都包含一种类似递增递乘的有规律的变化。）

就上来看，这两种递归调用都是无终止的自身调用，显然程序中不应出现这种无终止的递归调用，这就需要用if语句来控制，只有在某一条件成立时才继续执行递归调用，否则就不再继续。

下面我们用一个典型的函数递归调用的例子来说明：

用递归的方法求n!。

解题思路：

求n!可以用递归方法，即5！==4！*5，而4！==3！*4..........

可以用下面的递归公式表示

#include <stdio.h>
//求n的阶乘
int fac(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    else {int a;
        a=f(n - 1) * n;
        return a;  // 递归调用
    }
}
int main() {
    int a;
    printf("Input a number: ");
    scanf("%d", &a);
    printf("fac(%d) = %d\n", a, fac(a));
    return 0;
}

分析：

调用 fac() 后即进入函数体，只有当 n==0 或 n==1 时函数才会执行结束，否则就一直调用它自身。

由于每次调用的实参为 n-1，即把 n-1 的值赋给形参 n，所以每次递归实参的值都减 1，直到最后 n-1 的值为 1 时再作递归调用，形参 n 的值也为1，递归就终止了，会逐层退出。
 

要想理解递归函数，重点是理解它是如何逐层进入，又是如何逐层退出的，下面我们以 5! 为例进行讲解。

递归的进入

1) 求 5!，即调用 fac(5)。当进入 factorial() 函数体后，由于形参 n 的值为 5，不等于 0 或 1，所以执行fac(n-1) * n，也即执行fac(4) * 5。为了求得这个表达式的结果，必须先调用 fac(4)，并暂停其他操作。换句话说，在得到 factorial(4) 的结果之前，不能进行其他操作。这就是第一次递归。

2) 调用 fac(4) 时，实参为 4，形参 n 也为 4，不等于 0 或 1，会继续执行fac(n-1) * n，也即执行fac(3) * 4。为了求得这个表达式的结果，又必须先调用 fac(3)。这就是第二次递归。

3) 以此类推，进行四次递归调用后，实参的值为 1，会调用 fac(1)。此时能够直接得到常量 1 的值，并把结果 return，就不需要再次调用 fac() 函数了，递归就结束了。 

注意：递归结束时fac(1)满足if语句上半句，a被赋值为1，并且通过return语句将a=1返还给fac函数

即fac(1）=返还值（函数值）

递归的退出

当递归进入到最内层的时候，递归就结束了，就开始逐层退出了，也就是逐层执行 return 语句。

1) n 的值为 1 时达到最内层，此时 return 出去的结果为 1，也即 factorial(1) 的调用结果为 1。

2) 有了 fac(1) 的结果，就可以返回上一层计算fac(1) * 2的值了。此时得到的值为 2，return 出去的结果也为 2，也即 fac(2) 的调用结果为 2。

3) 以此类推，当得到 fac(4) 的调用结果后，就可以返回最顶层。经计算，fac(4) 的结果为 24，那么表达式fac(4) * 5的结果为 120，此时 return 得到的结果也为 120，也即 fac(5) 的调用结果为 120，这样就得到了 5! 的值。

希望对于初学的你一些启示！