4年前 (2020-10-03)  Java系列 |   抢沙发  1322 
文章评分 0 次，平均分 0.0 ：

这篇关于Java中递归的深入教程通过示例、类型和相关概念解释了什么是递归。它还包括递归与迭代：

从Java的早期教程中，我们已经看到了迭代方法，其中我们声明一个循环，然后通过一次获取一个元素以迭代的方式遍历数据结构。

我们还看到了一个条件流，其中我们保留一个循环变量并重复一段代码，直到循环变量满足条件为止。说到函数调用，我们还研究了函数调用的迭代方法。

Java中的递归是什么？

递归是一个函数或方法反复调用自身的过程。这种被反复直接或间接调用的函数称为“递归函数”。

我们将看到各种各样的例子来理解递归。现在让我们看看递归的语法。

递归语法

任何实现递归的方法都有两个基本部分：

  1. 可以调用自身的方法调用，即递归调用
  2. 停止递归的先决条件。

注意，任何递归方法都必须有一个先决条件，因为如果我们不中断递归，那么它将继续无限地运行并导致堆栈溢出。

递归的一般语法如下：

methodName (T parameters…)
{   
    if (precondition == true)           
 
//precondition or base condition
    {
        return result;
    }
    return methodName (T parameters…);
 
        //recursive call
}

请注意，前提条件也称为基本条件。

理解Java中的递归

在本节中，我们将尝试理解递归过程并了解它是如何发生的。我们将了解基本条件、堆栈溢出，并了解如何使用递归和其他类似的细节来解决特定问题。

递归基础条件

在编写递归程序时，我们应该首先为基本情况提供解决方案。然后我们用较小的问题来表示更大的问题。

作为一个例子，我们可以举一个计算一个数的阶乘的经典问题。给定一个数n，我们必须找到用n表示的n的阶乘！

现在让我们实现程序来计算n阶乘（n！）使用递归。

public class Main{
    static int fact(int n)
    {
        if (n == 1)
 
 // base condition
            return 1;
        else   
            return n*fact(n-1);    
    }    public static void main(String[] args) {
    int result = fact(10);
     
     System.out.println("10! = " + result);
    }
}

输出：

10 != 3628800

在这个程序中，我们可以看到条件（n<=1）是基本条件，当这个条件达到时，函数返回1。函数的另一部分是递归调用。但每次调用递归方法时，n都会递减1。

因此，我们可以得出结论，最终n的值将变为1或小于1，此时，该方法将返回值1。此基本条件将达到，功能将停止。注意，n的值可以是任何值，只要它满足基本条件。

使用递归解决问题

使用递归的基本思想是用较小的问题来表达更大的问题。另外，我们需要添加一个或多个基本条件，这样我们就可以摆脱递归。

在上面的阶乘例子中已经证明了这一点。在这个程序中，我们表示了n个阶乘（n！）对于较小的值，有一个基本条件（n<=1），因此当n达到1时，我们可以退出递归方法。

递归时出现堆栈溢出错误

我们知道，当调用任何方法或函数时，函数的状态存储在堆栈中，并在函数返回时进行检索。堆栈也用于递归方法。

但是在递归的情况下，如果我们不定义基条件，或者当基条件以某种方式未达到或执行时，可能会出现问题。如果出现这种情况，则可能出现堆栈溢出。

让我们考虑下面的阶乘表示法的例子。

这里我们给出了一个错误的基本条件，n==100。

public class Main
{
    static int fact(int n)
    {
        if (n == 100)
 
 // base condition resulting in stack overflow
            return 1;
        else   
            return n*fact(n-1);    
    }
public static void main(String[] args) {
    int result = fact(10);
     
        System.out.println("10! = " + result);
    }
}

所以当n>100时，方法将返回1，但递归不会停止。n的值将继续无限地递减，因为没有其他条件可以阻止它。这将一直持续到堆栈溢出。

另一种情况是n<100。在这种情况下，该方法也永远不会执行基本条件并导致堆栈溢出。

Java中的递归示例

在本节中，我们将使用递归实现以下示例。

使用递归的Fibonacci级数

斐波那契级数由，

1,1,2,3,5,8,13,21,34,55，…

上面的序列显示当前元素是前两个元素的和。另外，Fibonacci级数的第一个元素是1。

一般来说，如果n是当前数，那么它由（n-1）和（n-2）之和给出。由于当前元素是用以前的元素表示的，所以我们可以使用递归来表示这个问题。

实现Fibonacci级数的程序如下所示：

public class Main
{
    //method to calculate fibonacci series
    static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    }
    public static void main(String[] args) {
        int number = 10;
  
        //print first 10 numbers of fibonacci series
        System.out.println ("Fibonacci Series: First 10 numbers:");
        for (int i = 1; i <= number; i++) 
        {
            System.out.print(fibonacci(i) + " ");
        }
  
}
}

输出：

Fibonacci Series: First 10 numbers:

1 1 2 3 5 8 13 21 34 55

使用递归检查数字是否为回文Palindrome

回文是从左到右或从右到左读它的序列是相等的。

给定一个数字121，当我们从左到右和从右到左读时，它是相等的。因此，数字121是一个回文Palindrome。

我们换一个号码，1242。从左到右读是1242，从右向左读是2421。因此这不是回文。

我们通过反转数字的位数来实现回文程序，并递归地将给定的数字与其反向表示进行比较。

下面的程序实现了检查回文Palindrome的程序。

import java.io.*; 
import java.util.*; 
    
public class Main { 
    // check if num contains only one digit 
    public static int oneDigit(int num) { 
         if ((num >= 0) && (num < 10)) 
            return 1; 
        else
            return 0; 
    } 
   //palindrome utility function
    public static int isPalindrome_util (int num, int revNum) throws Exception { 
           // base condition; return if num=0
        if (num == 0) { 
            return revNum; 
        } else { //call utility function recursively
            revNum = isPalindrome_util(num / 10, revNum); 
        } 
         // Check if first digit of num and revNum are equal 
        if (num % 10 == revNum % 10) { 
            // if yes, revNum will move with num
            return revNum / 10; 
        }
else { 
            // exit 
            throw new Exception(); 
        } 
    } 
    //method to check if a given number is palindrome using palindrome utility function
    public static int isPalindrome(int num)  throws Exception { 
        if (num < 0) 
            num = (-num); 
    
        int revNum = (num); 
        return isPalindrome_util(num, revNum); 
    } 
    
    public static void main(String args[]) { 
        int n = 1242; 
        try { 
            isPalindrome(n); 
            System.out.println("Yes, the given number " + n + " is a palindrome."); 
        } catch (Exception e) { 
            System.out.println("No, the given number " + n + " is not a palindrome."); 
        } 
        n = 1221; 
        try { 
            isPalindrome(n); 
            System.out.println("Yes, the given number " + n + " is a palindrome."); 
        } catch (Exception e) { 
            System.out.println("No, the given number " + n + " is not a palindrome."); 
        } 
    } 
}

输出：

No, the given number 1242 is not a palindrome.

Yes, the given number 1221 is a palindrome.

反向字符串递归Java

给定一个字符串Hello，我们必须将其反转，以使结果字符串为olleH。

这是通过递归完成的。从字符串中的最后一个字符开始，我们递归地打印每个字符，直到字符串中的所有字符用完为止。

下面的程序使用递归来反转给定的字符串。

class String_Reverse 
{ 
    //recursive method to reverse a given string
    void reverseString(String str) 
    { 
        //base condition; return if string is null or with 1 or less character 
        if ((str==null)||(str.length() <= 1)) 
           System.out.println(str); 
        else
        { 
            //recursively print each character in the string from the end 
            System.out.print(str.charAt(str.length()-1)); 
            reverseString(str.substring(0,str.length()-1)); 
        } 
    }
}
class Main{
    public static void main(String[] args)  
    { 
        String inputstr = "SoftwareTestingHelp";
        System.out.println("The given string: " + inputstr);
        String_Reverse obj = new String_Reverse(); 
        System.out.print("The reversed string: ");
        obj.reverseString(inputstr); 
          
    }     
}

输出：

The given string: SoftwareTestingHelp

The reversed string: pleHgnitseTerawtfoS

二进制搜索Java递归

二进制搜索算法是一种著名的搜索算法。在这个算法中，给定n个元素的排序数组，我们在这个数组中搜索给定的键元素。首先，我们通过找到数组的中间元素将数组分成两半。

然后根据key<mid还是key>mid，我们将搜索限制在数组的前半部分还是后半部分。这样，重复相同的过程，直到找到关键元素的位置。

我们将在这里使用递归实现这个算法。

import java.util.*;
class Binary_Search { 
    // recursive binary search
    int binarySearch(int numArray[], int left, int right, int key)   { 
        if (right >= left) { 
            //calculate mid of the array
            int mid = left + (right - left) / 2; 
             // if the key is at mid, return mid 
            if (numArray[mid] == key) 
                return mid; 
             // if key < mid, recursively search the left subarray
            if (numArray[mid] > key) 
                return binarySearch(numArray, left, mid - 1, key); 
             // Else recursively search in the right subarray
            return binarySearch(numArray, mid + 1, right, key); 
        } 
        // no elements in the array, return -1 
        return -1; 
    } 
}
class Main{
    public static void main(String args[])   { 
        Binary_Search ob = new Binary_Search(); 
        //declare and print the array
        int numArray[] = { 4,6,12,16,22}; 
        System.out.println("The given array : " + Arrays.toString(numArray));
        int len = numArray.length;              //length of the array
        int key = 16;                           //key to be searched 
        int result = ob.binarySearch(numArray, 0, len - 1, key); 
        if (result == -1) 
            System.out.println("Element " + key + " not present"); 
        else
            System.out.println("Element " + key + " found at index " + result); 
    } 
}

输出：

The given array : [4, 6, 12, 16, 22]

Element 16 found at index 3

使用递归查找数组中的最小值

使用递归，我们还可以找到数组中的最小值。

下面给出了在数组中查找最小值的Java程序。

import java.util.*;
class Main  
{ 
static int getMin(int numArray[], int i, int n) 
{ 
    //return first element if only one element or minimum of the array elements
    return (n == 1) ? numArray[i] : 
        Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); 
} 
   
public static void main(String[] args)  
{ 
    int numArray[] = { 7,32,64,2,10,23 }; 
    System.out.println("Given Array : " + Arrays.toString(numArray));
    int n = numArray.length; 
    System.out.print("Minimum element of array: " + getMin(numArray, 0, n) + "\n"); 
} 
}

输出：

Given Array : [7, 32, 64, 2, 10, 23]

Minimum element of array: 2

这些是递归的一些例子。除了这些例子，软件中的许多其他问题都可以使用递归技术来实现。

递归类型

递归有两种类型，基于调用递归方法的时间。

尾递归

当对递归方法的调用是递归方法内部执行的最后一条语句时，称为“尾部递归”。

在尾部递归中，递归调用语句通常与方法的return语句一起执行。

尾部递归的一般语法如下：

methodName ( T parameters…){
{   
    if (base_condition == true)
    {
        return result;
    }
    return methodName (T parameters …)      //tail recursion
}

头递归

头递归是任何不是尾递归的递归方法。所以，即使是一般的递归也比递归超前。

头递归的语法如下：

methodName (T parameters…){
    if (some_condition == true)
    {
        return methodName (T parameters…);
    }
    return result;
}

更多递归示例请参考这篇文章：https://javakk.com/508.html

Java中的递归与迭代区别:

如何编写Java递归函数？

总结

递归是软件中一个非常重要的概念，与编程语言无关。递归主要用于解决数据结构问题，如Hanoi塔、树遍历、链表等。虽然递归占用更多内存，但递归使代码更简单、更清晰。

  
 

除特别注明外，本站所有文章均为老K的Java博客原创，转载请注明出处来自https://javakk.com/517.html

关于
上一篇  
下一篇  

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册

繁