Java的递归算法

全栈程序员-站长 • 2021年12月10日下午3:00 • 未分类 • 阅读 39

大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。

递归算法设计的基本思想是：对于一个复杂的问题，把原问题分解为若干个相对简单类同的子问题，继续下去直到子问题简单到可以直接求解，也就是说到了递推的出口，这样原问题就有递推得解。

关键要抓住的是：

（1）递归出口

（2）地推逐步向出口逼近

样例:

example：求5的阶乘。。



例如以下：

Java代码

public class Test {
static int multiply(int n){
if(n==1||n==0)
return n;
else
return n*multiply(n-1);
}
public static void main(String[] args){
System.out.println(multiply(10));
}
}

public class Test {      
static int multiply(int n){      
if(n==1||n==0)      
return n;      
else      
return n*multiply(n-1);      
}      
   
public static void main(String[] args){      
System.out.println(multiply(10));      
}      
}

上面的multiply是一个阶乘的样例。事实上递归递归，从字面上解释就是在方法本身调用自己的方法，或者间接调用；看上面的程序，拿multiply(5)来说：

n=5;运行 5*multiply(4);

——————–

这时候看multiply(4)

n=4 运行 4*multiply(3);

——————-

看multiply(3)

n=3,运行 3*multiply(2);

—————

mulitply(2);

n=2 运行 2*mulitply(1);

这时候，return 1;往上返回

2*1向上返回

3*(2*1)向上返回

4*（3*（2*1））向上返回

5*（4*（3*（2*1））） = 120

所以程序输出120;

这事简单的递归的样例；所以能够看出来递归的关键得有递归出口(本体的If语句)，还有递归方法；

下面是我在百度知道碰到一个朋友的提问,也是关于递归算法的:

————————问题——————————

本人刚学JAVA，没有不论什么编程基础，各位高手见笑。

Java代码

public class Count
{
static void count(int n) //递归方法
{
if (n<5)
count(n+1);
System.out.print(” “+n);
}
public static void main(String args[])
{
count(1);
System.out.println();
}
}

public class Count
{
    static void count(int n)               //递归方法
    {
        if (n<5) 
            count(n+1); 
        System.out.print("     "+n);
    } 
    public static void main(String args[])
    {
        count(1);
        System.out.println();
    }
}

请具体解说这段程序是怎么运行的，我的理解是先运行main函数里的count(1),然后进入count方法，N值为1，所以运行IF语句，直到count(5),此时退出if 循环，打印N=5 ，然后应该没有要运行的东西了，但是答案是5 4 3 2 1 ，请问这是怎么回事，谢谢！

——————–回答—————————

先运行count(1)，然后进入count方法，N值为1，所以运行IF语句，也就是运行count(2),然后进入count方法，N值为2，所以运行IF语句，也就是运行count(3),然后进入count方法，N值为3，所以运行IF语句，也就是运行count(4),然后进入count方法，N值为4，所以运行IF语句，也就是运行count(5),然后进入count方法，N值为5，所以不运行IF语句，然后运行System.out.print(” “+n); 也就是输出5，然后本次參数为5的count方法调用结束了，返回到调用它的參数为4的count方法中，然后运行System.out.print(” “+n);输出4，然后一直这样下去，输出3，2，1 。这里须要说明的是在运行count(5)的时候，count(4)、count(3)、count(2)、count(1)都没有运行完成，他们都在等自己方法体中的count(n+1)运行完成，然后再运行System.out.print(” “+n);

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118127.html原文链接：https://javaforall.net