/*
SilniaDZ.java
Mówimy, że wywołanie metody jest wywołaniem rekurencyjnym,
jeśli metoda wywołuje samą siebie. Innymi słowy, jeżeli w
ciele danej metody znajduje się wywołanie tej samej metody,
to jest to wywołanie rekurencyjne. W poniższym programie
rekurencyjnie wywoływana jest metoda silnia, która oblicza
wartość silni na podstawie wzoru rekurencyjnego:
0! = 1
n! = n*(n-1)!
*/
public class SilniaDZ
{
public static void main(String[] args)
{
final int N = 3;
System.out.println(N + "! = " + silnia(N));
}
static long silnia(int n)
{
if (n == 0)
{
return 1;
}
else
{
return n*silnia(n-1); // silnia(n-1) wywołanie rekurencyjne
}
}
}
3! = 6 Press any key to continue...
Dokonaj analizy wywołania silnia(3) w programie SilniaDZ.
Uwaga: Kolejne wywołania metody silnia zostały ponumerowane przy pomocy indeksów dolnych.
silnia1(3) --> silnia2(2) --> silnia3(1) --> silnia4(0)
Opis wywołań podamy na przykładzie wywołania silnia(0) i silnia(1)
• silnia(0) - wywołujemy metodę silnia z parametrem aktualnym 0
- w momencie wywołania metody silnia parametr formalny n przyjmuje wartość
parametru aktualnego, czyli 0
- wchodzimy do ciała metody silnia, napotykamy instrukcję if..else, sprawdzamy
warunek logiczny z nagłówka instrukcji, warunek jest prawdziwy, bo 0 = 0,
a zatem wchodzimy do pierwszego ciała instrukcji
- w pierwszym ciele instrukcji if..else zwracamy wartość 1
• silnia(1) - wywołujemy metodę silnia z parametrem aktualnym 1
- w momencie wywołania metody silnia parametr formalny n przyjmuje wartość
parametru aktualnego, czyli 1
- wchodzimy do ciała metody silnia, napotykamy instrukcję if..else, sprawdzamy
warunek logiczny z nagłówka instrukcji, warunek jest fałszywy, bo 1 ≠ 0,
a zatem pomijamy pierwsze ciało i wchodzimy do drugiego ciała instrukcji
- w drugim ciele instrukcji if..else zwracamy wartość wyrażenie 1*silnia(0)
w którym pojawia się wywołanie rekurencyjne silnia(0)
/* Polinomial.java */
public class Polinomial
{
public static void main(String[] args)
{
double[] a = {1,2,3,4}; // 1 + 2x + 3x^2 + 4x^3
double x = 0.5;
System.out.println("w(" + x + ") = " + w(a,x));
}
static double potega(double x, int n)
{
if (n == 1)
{
return x;
}
else
{
return x * potega(x, n-1);
}
}
static double w(double[] a, double x)
{
if (a.length == 0) return 0;
return polinomial(a, x, a.length-1);
}
static double polinomial(double[] a, double x, int i)
{
if (i == 0)
{
return a[0];
}
else
{
return polinomial(a, x, i-1) + a[i] * potega(x, i);
}
}
}
w(0.5) = 3.25 Press any key to continue...
Dokonaj analizy wywołania w(a,0.5) w programie Polinomial.
0 1 2 3
a --> [1][2][3][4]
a.length = 4
Analizujemy wywołanie w(a,0.5).
• w1(a, 0.5) = 3.25 4 == 0 false return polinomial2(a, 0.5, 3) = 3.25
• polinomial2(a, 0.5, 3) = 3.25 return polinomial3(a, 0.5, 2) + a[3] * potega9(0.5, 3) = 2.75 + 4.0 * 0.125 = 2.75 + 0.5 = 3.25
• polinomial3(a, 0.5, 2) = 2.75 return polinomial4(a, 0.5, 1) + a[2] * potega7(0.5, 2) = 2.0 + 3.0 * 0.25 = 2.75
• polinomial4(a, 0.5, 1) = 2.0 return polinomial5(a, 0.5, 0) + a[1] * potega6(0.5, 1) = 1.0 + 2.0 * 0.5 = 2.0
• polinomial5(a, 0.5, 0) = 1.0 return a[0] = 1.0
• potega6(0.5, 1) = 0.5 return 0.5
• potega7(0.5, 2) = 0.25 return 0.5 * potega8(0.5, 1) = 0.5 * 0.5 = 0.25
• potega8(0.5, 1) = 0.5 return 0.5
• potega9(0.5, 3) = 0.125 return 0.5 * potega10(0.5, 2) = 0.5 * 0.25 = 0.125
• potega10(0.5, 2) = 0.25 return 0.5 * potega11(0.5, 1) = 0.5 * 0.5 = 0.25
• potega11(0.5, 1) = 0.5 return 0.5
Uwaga: Kolejne wywołania metod zostały ponumerowane przy pomocy indeksów dolnych.
/*
FiboDZ.java
W poniższym programie metoda fibo wyznacza n-ty wyraz
ciągu Fibonacciego na podstawie wzoru rekurencyjnego
fibo(n) = 1 dla n = 1
fibo(n) = 1 dla n = 2
fibo(n) = fibo(n-1) + fibo(n-2) dla n > 2
Dwa pierwsze wyrazy ciągu Fibonacciego mają wartość
1 a każdy kolejny wyraz jest sumą dwóch poprzednich.
Ciąg Fibonacciego: 1, 1, 2, 3, 5, 8, 13, 21, ...
*/
public class FiboDZ
{
public static void main(String[] args)
{
final int N = 5;
System.out.println("fibo(" + N + ") = " + fibo(N));
}
static int fibo(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
else
{
return fibo(n-1) + fibo(n-2); // dwa wywołania rekurencyjne
}
}
}
fibo(5) = 5 Press any key to continue...
Dokonaj analizy wywołania fibo(5) w programie FiboDZ.
fibo1(5)
/ \
/ \
fibo2(4) fibo7(3)
/\ /\
/ \ / \
fibo3(3) fibo6(2) fibo8(2) fibo9(1)
/\
/ \
fibo4(2) fibo5(1)
Dokonaj analizy wywołania fibo(5) w programie FiboDZ.
fibo1(5)
/ \
/ \
fibo2(4) fibo7(3)
/\ /\
/ \ / \
fibo3(3) fibo6(2) fibo8(2) fibo9(1)
/\
/ \
fibo4(2) fibo5(1)
/*
FiboDZ2.java
Poniższy program wypisuje, jak wyglądają kolejne
wywołania rekurencyjne. Na ich podstawie możemy
zweryfikować analizę wywołań rekurencyjnych.
*/
public class FiboDZ2
{
private static int wywolanie;
public static void main(String[] args)
{
final int N = 5; fibo(N);
}
static int fibo(int n)
{
wywolanie++;
System.out.println("fibo" + wywolanie + "(" + n + ") = " + f(n));
if (n == 1 || n == 2)
{
return 1;
}
else
{
return fibo(n-1) + fibo(n-2); // dwa wywołania rekurencyjne
}
}
static int f(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
else
{
return f(n-1) + f(n-2);
}
}
}
fibo1(5) = 5 fibo2(4) = 3 fibo3(3) = 2 fibo4(2) = 1 fibo5(1) = 1 fibo6(2) = 1 fibo7(3) = 2 fibo8(2) = 1 fibo9(1) = 1 Press any key to continue...