递归的定义：

• 在定义一个过程或方法时出现调用本过程或本方法的成分，称之为递归。
• 若调用自身，称之为直接递归。
• 若过程或方法A调用过程或方法B，而B又调用A，称之为间接递归.
• 在算法设计中，任何间接递归算法都可以转换为直接递归算法来实现，所以主要讨论直接递归。
• 如果一个递归过程或递归方法中递归调用语句是最后一条执行语句，称为尾递归。

例题：

【例】以下是求n! (n为正整数）的递归方法。它属于什么类型的递归。

int fun( int n)
{    if (n==1)                            //语句1
        return(1);                        //语句2
    else                                //语句3
        return(fun(n-1)*n);                //语句4
}

解：直接递归方法。又由于递归调用是最后一条语句，所以它又属于尾递归

递归算法通常把一个大的复杂问题层层转化为一个或多个与原问题相似的规模较小的问题来求解。

递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了算法的代码量。

一般来说，能够用递归解决的问题应该满足以下3个条件：

• 需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。
• 递归调用的次数必须是有限的。
• 必须有结束递归的条件来终止递归。

何时使用递归：

• 有许多数学公式、数列等的定义是递归的。例如，求n!和Fibonacci(斐波那契）数列等。

int fib1(int n)            //求Fibonacci数列的第n项
{ if (n==1 ll n==2)
        return 1;
    else
        return fib1(n-1) +fib1(n-2);
}

• 有些数据结构是递归的。如单链表就是一种递归数据结构。

class LinkNode<E>        //单链表结点泛型类
{     E data;
    LinkNode<E> next;    //下一个结点的指针
    public LinkNode()    //构造方法
    {next=null;}
    public LinkNode(E d)    //重载构造方法
    {     data=d;
        next=null;
    }
}

• 求一个不带头结点单链表p中所有data成员（假设为int型）之和。

public static int sum( LinkNode<Integer> p)
{     if (p==null)
        return 0;
     else
        return(p.data + sum(p.next)) ;
}

• 递归模型是递归算法的抽象，它反映一个递归问题的递归结构。

int fun(int n)
{     if (n==1)            //语句1
    return(1);            //语句2
        else            //语句3
    return(fun(n-1)*n);    //语句4
}

• 递归模型：

上面的递归模型：
f(n)=1                    n=1
f(n)=n*f(n-1)            n>1

• 一般地，一个递归模型是由递归出口和递归体两部分组成。
• 递归出口确定递归到何时结束，即指出明确的递归结束条件。
• 递归体确定递归求解时的递推关系。