浅析递归调用

递归调用算法

递归调用算法指的是一函数不断调用自身的算法。需要说明的是：递归算法并非一碰到return就结束调用，而是由被调函数一层层返回主函数。

递归函数体

递归函数体包含两部分：

1.递归头（说明递归结束的条件）

2.递归体（使用递归需要执行的操作，如：改变入参）

递归算法实例

问题：求给定整数的下一个质数,如果自身是质数，则返回自身

例：

INPUT:7 OUTPUT:7

INPUT:8 OUTPUT:11

算法代码（java）

package test;

import java.util.Scanner;

public class test002 {

    public int find(int x){
        if(x<=1){
            System.out.println("输入有误！");
        }
        boolean flag = true;
        for(int i=2; i<=Math.sqrt(x); i++){

            if(x%i==0){
                flag = false;
                break;
            }
        }
        if(!flag)
            return find(++x);   /*需要特别注意这里加了return,这里也是递归体*/

        return x;
    }


    public static void main(String[] args){
        Scanner in = new Scanner(System.in); 
        int x;
        System.out.println("请输入数值： ");
        x = in.nextInt();
        test002 newtest = new test002();
        System.out.println(newtest.find(x));
    }
}

上面find递归函数里，有包含两个return，第一个return返回递归体，第二个return返回参数x的值。

若第一个不加return，则函数到了结束条件时，会一层层地向上返回，直到返回到原来的主调函数。

e.g. 输入为8，期望输出为11。

1.若递归体调用find函数时不加return，即由 return find(++x) 变为 find(++x) ，则x的值变为11后，先执行return x，然后find函数会一层层地返回到原来的主调函数，即

find(11);
return 11;
find(10);
return 10;
find(9);
return 9;

最后只能到find(9)，因为递归体入参是 find(++x) .最后返回 9。

2.若第一个加了return，即 return find(++x) 则x的值变为11后，先执行return x ，然后直接执行return find(++x)语句，跳出当前递归。