Rekursion i Java
Rekursion er kernen i programmering og bruges i mange relaterede begreber som sortering, trægennemgang og grafer. Derudover har rekursion en bred vifte af anvendelser i datastrukturer og algoritmer, og selvom det er et komplekst koncept, kan det bruges til at gøre opgaven nemmere.
Rekursion er med enkle ord en funktion, der kalder sig selv. Lad os se vores første kode, som bogstaveligt talt beskriver definitionen.
Rekursion i Java
/**
This class has a recursive method.
*/
public class EndlessRecursion
{
public static void message()
{
System.out.println("This is a recursive method.");
//recursive call
message();
}
} Ovenstående kode er ret simpel. Vi har et klassekald endeløs rekursion med en funktion med navnet besked, og funktionen udskriver linjen "Dette er en rekursiv metode". Der er dog et problem. Der er ingen måde at stoppe de rekursive opkald. Så denne metode er som en uendelig løkke, fordi der ikke er nogen kode, der forhindrer den i at gentages. Så vi konkluderede, at en rekursiv funktion også kræver en termineringsbetingelse for at stoppe, ligesom en loop.
En simpel kode er vist nedenfor med en opsigelsesbetingelse.
/**
This class has a recursive method, message,
which displays a message n times.
*/
public class Recursive
{
public static void message(int n)
{
if (n > 0)
{
System.out.println("This is a recursive method.");
message(n - 1);
//After the condition is false the control returns to the end of the if
//expression and since no statement is written below the recursive
//call, the method returns.
}
}
} Nu indeholder metodebeskeden() en if-betingelse, der styrer gentagelsen af funktionen. Så længe parameteren n er større end nul, viser metoden beskeden og kalder sig selv igen. Lad os overveje, at n=5 i dette tilfælde. Således vil funktionen message() kalde sig selv 5 gange og vise indholdet af print-sætningen. Antallet af gange, en metode kaldes, er dybden af rekursion. I dette tilfælde er dybden af rekursion 5. Når metoden når det sjette kald, er n=0. På det tidspunkt er if-sætningens betingede udtryk falsk, så metoden vender tilbage.
Løsning af problemer med rekursion
Rekursion kan være et kraftfuldt værktøj til at løse gentagne problemer og er et vigtigt emne i datalogikurser på øverste niveau. Hvad der måske ikke er klart for dig endnu, er, hvordan du bruger rekursion til at løse et problem. Ethvert problem, der kan løses rekursivt, kan også løses ved hjælp af en loop. Faktisk er rekursive løsninger mindre effektive sammenlignet med iterative løsninger. Rekursion er dog stadig meget brugt, fordi det gør jobbet som programmør lettere.
Generelt fungerer en rekursiv metode sådan her:
• Hvis problemet kan løses uden rekursion, så løser metoden det
og vender tilbage.
• Hvis problemet ikke kan løses, så reducerer metoden det til et mindre men
lignende problem og kalder sig selv for at løse det mindre problem.
For at anvende dette skal vi identificere mindst ét tilfælde, hvor problemet kan løses uden rekursion, og dette er kendt som basissagen. Derefter bestemmer vi en måde at løse problemet under alle andre omstændigheder ved hjælp af rekursion. Lad os endelig overveje en kode, der beskriver denne rekursive metode.
/**
The factorial method uses recursion to calculate
the factorial of its argument, which is assumed
to be a nonnegative number.
@param n The number to use in the calculation.
@return The factorial of n.
*/
private static int factorial(int n)
{
if (n == 0)
return 1; // Base case
else
//Although this is a return statement, it does not immediately return. Before the return value
//can be determined, the value of factorial(n − 1) must be determined. The factorial
//method is called recursively until the n parameter will be set to zero.
return n * factorial(n - 1);
}Berømte rekursive problemer
Nogle velkendte rekursive problemer omfatter Fibonacci-serier, factorial, Greatest common divisor, binær søgning og mange flere.
Lad os starte med det enkleste, altså Fibonacci-serien. Fibonacci-serien er en sekvens, der ser nogenlunde sådan ud.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, . . .
Bemærk, at hvert tal i serien er summen af de to foregående tal efter det andet tal. Således kan Fibonacci-serien defineres som følger.
public static int fib(int n)
{
//base case 1
if (n == 0)
return 0;
//base case 2
else if (n == 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}Lad os skrive hele koden for at teste denne funktion
/**
This program demonstrates the recursive fib method.
*/
public class FibNumbers
{
public static void main(String[] args)
{
System.out.println("The first 10 numbers in " +
"the Fibonacci series are:");
for (int i = 0; i < 10; i++)
System.out.print(fib(i) + " ");
System.out.println();
}
/**
The fib method calculates the nth
number in the Fibonacci series.
@param n The nth number to calculate.
@return The nth number.
*/
public static int fib(int n)
{
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fib(n − 1) + fib(n − 2);
}
} Dernæst kommer den største fælles divisor, dvs. GCD.
GCD for to positive heltal, x og y, er som følger:
hvis y deler x ligeligt, så er gcd(x, y) =y
Ellers er gcd(x, y) =gcd(y, resten af x/y)
Denne definition angiver, at GCD af x og y er y, hvis x/y ikke har nogen rest. Dette er grundsagen. Ellers er svaret GCD af y og resten af x/y.
import java.util.Scanner;
/**
This program demonstrates the recursive gcd method.
*/
public class GCDdemo
{
public static void main(String[] args)
{
int num1, num2; // Two numbers for GCD calculation
// Create a Scanner object for keyboard input.
Scanner keyboard = new Scanner(System.in);
// Get the first number from the user.
System.out.print("Enter an integer: ");
num1 = keyboard.nextInt();
// Get the second number from the user.
System.out.print("Enter another integer: ");
num2 = keyboard.nextInt();
// Display the GCD.
System.out.println("The greatest common divisor " +
"of these two numbers is " +
gcd(num1, num2));
}
/**
The gcd method calculates the greatest common
divisor of the arguments passed into x and y.
@param x A number.
@param y Another number.
@returns The greatest common divisor of x and y.
*/
public static int gcd(int x, int y)
{
if (x % y == 0)
return y;
else
return gcd(y, x % y);
}
} Outputtet af ovenstående program er
Enter an integer: 49 [Enter]
Enter another integer: 28 [Enter]
The greatest common divisor of these two numbers is 7Konklusion
Alle metoderne beskrevet ovenfor har en iterativ løsning, men den rekursive løsning skaber en elegant og nem skriveløsning. I datastrukturer som træer og grafer er rekursive kald udbredte, fordi de gør koden kortfattet og let at forstå.
