1 Rekursja Teoretyczne podstawy informatyki Wykład 5(c) Jerzy Nawrocki TPI, Wykład 5 Teoretyczne podstawy informatyki Wykład 5 Rekursja Copyright, 2004 © Jerzy R. Nawrocki Rekursja

2 Dodać rozwiązanie problemu podziału zbioru (wersja rekurencyjna) (c) Jerzy Nawrocki Ulepszenia TPI, Wykład 5 Dodać rozwiązanie problemu podziału zbioru (wersja rekurencyjna) Dodać instrukcje asemblera dot. Wywoływania podprogramów i rekursji. Zostało mi ok. minut. J.Nawrocki, Rekursja Rekursja

3 Silnia Plan wykładu Wielomian Liczby Fibonacciego Operacja minimumJ.Nawrocki, Rekursja

4 Definiowanie indukcyjneWprowadzenie Masło maślane Definiowanie indukcyjne (rekursja / rekurencja): definiujemy nieznane przez nieznane, które będzie znane J.Nawrocki, Rekursja

5 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n 0! = 1 1 1! = 1 2 2! = 2 3 3! = 6 4 4! = 24 J.Nawrocki, Rekursja

6 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n begin end. J.Nawrocki, Rekursja

7 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n begin read(n); end. J.Nawrocki, Rekursja

8 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n var n: integer; begin read(n); end. J.Nawrocki, Rekursja

9 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n var n: integer; begin read(n); writeln(n, ‘! = ’, S(n) ) end. J.Nawrocki, Rekursja

10 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n var n: integer; begin read(n); writeln(n, ‘! = ’, S(n) ) end. J.Nawrocki, Rekursja

11 Napisz program obliczania n!Silnia Napisz program obliczania n! 3 n! = 1*2*3* .. * (n-1) * n var n: integer; begin read(n); writeln(n, ‘! = ’, S(n) ) end. J.Nawrocki, Rekursja

12 Napisz program obliczania n!Silnia Napisz program obliczania n! 3 n! = 1*2*3* .. * (n-1) * n var n: integer; begin read(n); writeln(n, ‘! = ’, S(n) ) end. J.Nawrocki, Rekursja

13 Napisz program obliczania n!Silnia Napisz program obliczania n! 3 n! = 1*2*3* .. * (n-1) * n var n: integer; begin read(n); writeln(n, ‘! = ’, S(n) ) end. 3 J.Nawrocki, Rekursja

14 Napisz program obliczania n!Silnia Napisz program obliczania n! 3 n! = 1*2*3* .. * (n-1) * n var n: integer; begin read(n); writeln(n, ‘! = ’, S(n) ) end. 3 3! = 6 J.Nawrocki, Rekursja

15 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n var n: integer; begin read(n); writeln(n, ‘! = ’, S(n) ) end. J.Nawrocki, Rekursja

16 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n function S(n: integer): integer; var n: integer; begin read(n); writeln(n, ‘! = ’, S(n) ) end. S(n) = jeśli n=0 S(n) = S(n-1)*n jeśli n>0 S(0) = 1 S(n) = S(n-1)*n 0! = 1 n! = (n-1)! * n J.Nawrocki, Rekursja

17 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n function S(n: integer): integer; begin end; var n: integer; read(n); writeln(n, ‘! = ’, S(n) ) end. S(n) = jeśli n=0 S(n) = S(n-1)*n jeśli n>0 J.Nawrocki, Rekursja

18 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n function S(n: integer): integer; begin end; var n: integer; read(n); writeln(n, ‘! = ’, S(n) ) end. S(n) = jeśli n=0 S(n) = S(n-1)*n jeśli n>0 J.Nawrocki, Rekursja

19 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n function S(n: integer): integer; begin if n = 0 then S:= 1; end; var n: integer; read(n); writeln(n, ‘! = ’, S(n) ) end. S(n) = jeśli n=0 S(n) = S(n-1)*n jeśli n>0 J.Nawrocki, Rekursja

20 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n function S(n: integer): integer; begin if n = 0 then S:= 1; end; var n: integer; read(n); writeln(n, ‘! = ’, S(n) ) end. S(n) = jeśli n=0 S(n) = S(n-1)*n jeśli n>0 J.Nawrocki, Rekursja

21 Napisz program obliczania n!Silnia Napisz program obliczania n! n! = 1*2*3* .. * (n-1) * n function S(n: integer): integer; begin if n = 0 then S:= 1; if n > 0 then S:= S(n-1) * n; end; var n: integer; read(n); writeln(n, ‘! = ’, S(n) ) end. S(n) = jeśli n=0 S(n) = S(n-1)*n jeśli n>0 J.Nawrocki, Rekursja

22 Liczba cyfr LCyfr(0) = 1 LCyfr(1) = 1 . . . LCyfr(9) = 1LCyfr(n) = 1 + LCyfr(n/10) J.Nawrocki, Rekursja

23 P(a, b) = ab dla naturalnych a,bFunkcja potęgowa P(a, b) = ab dla naturalnych a,b P(a, 0) = 1 P(a, b) = P(a, b-1) * a J.Nawrocki, Rekursja

24 Silnia Program w Pascalu We n Wyfunction S(n: integer): integer; begin 3 if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; begin read(n); writeln( S(n) ) end. J.Nawrocki, Rekursja

25 Silnia Program w Pascalu We n Wy 3function S(n: integer): integer; begin 3 3 if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; begin read(n); writeln( S(n) ) end. J.Nawrocki, Rekursja

26 Parametry + zmienne lokal.Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) *n Parametry + zmienne lokal. Instrukcje function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. Instancja funkcji J.Nawrocki, Rekursja

27 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) *nfunction S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. J.Nawrocki, Rekursja

28 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) *n S: n=2 if n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. J.Nawrocki, Rekursja

29 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 if n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. J.Nawrocki, Rekursja

30 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 if n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S(n-1) S: n=0 if n=0 then S:= 1 else S:= S(n-1) * n J.Nawrocki, Rekursja

31 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 if n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S(n-1) S: n=0 if n=0 then S:= 1 else S:= S(n-1) * n J.Nawrocki, Rekursja

32 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 if n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S(n-1) S: n=0 S=1 if n=0 then S:= 1 else S:= S(n-1) * n J.Nawrocki, Rekursja

33 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 if n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. 1 J.Nawrocki, Rekursja

34 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 if n=0S: n=1 S=1 if n=0 then S:= 1 else S:= S(n-1) * n function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. 1 J.Nawrocki, Rekursja

35 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 if n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. J.Nawrocki, Rekursja

36 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 S=2 if n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. J.Nawrocki, Rekursja

37 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n 2function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. J.Nawrocki, Rekursja

38 Silnia S: n=3 S=6 if n=0 then S:= 1 else S:= S(n-1) * n 2function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. J.Nawrocki, Rekursja

39 Silnia Program w Pascalu We n Wy 3 6function S(n: integer): integer; begin 3 3 6 if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; begin read(n); writeln( S(n) ) end. J.Nawrocki, Rekursja

40 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 if n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S(n-1) S: n=0 if n=0 then S:= 1 else S:= S(n-1) * n J.Nawrocki, Rekursja

41 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 if n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S(n-1) S: n=0 J.Nawrocki, Rekursja

42 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 if n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S: n=0 J.Nawrocki, Rekursja

43 Silnia S: n=3 if n=0 then S:= 1 else S:= S(n-1) * n S: n=2 S(n-1)function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S: n=0 J.Nawrocki, Rekursja

44 Silnia S: n=3 S: n=2 S: n=1 S: n=0 function S(n: integer):integ beginif n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S: n=0 J.Nawrocki, Rekursja

45 Silnia S: n=3 else S: n=2 S: n=1 S: n=0 function S(n: integer):integbegin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S: n=0 J.Nawrocki, Rekursja

46 Silnia S: n=3 else S: n=2 else S: n=1 S: n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S: n=0 J.Nawrocki, Rekursja

47 Silnia S: n=3 else S: n=2 else S: n=1 else S: n=0function S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S: n=0 J.Nawrocki, Rekursja

48 Silnia S: n=3 else S: n=2 else S: n=1 else S: n=0 thenfunction S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S: n=0 then J.Nawrocki, Rekursja

49 Silnia S: n=3 else S: n=2 else S: n=1 else S: n=0 thenfunction S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S: n=0 then J.Nawrocki, Rekursja

50 Silnia S: n=3 else S: n=2 else S: n=1 else S: n=0 thenfunction S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S: n=0 then J.Nawrocki, Rekursja

51 Silnia S: n=3 else S: n=2 else S: n=1 else S: n=0 thenJ.Nawrocki, Rekursja

52 Silnia S: n=3 else S: n=2 else S: n=1 else S: n=0 thenJ.Nawrocki, Rekursja

53 Silnia S: n=3 else S: n=2 else S: n=1 else S: n=0 thenJ.Nawrocki, Rekursja

54 Silnia S: n=2 else S: n=1 else S: n=0 then S: n=3 elseJ.Nawrocki, Rekursja

55 Silnia S: n=1 else S: n=2 else S: n=0 then S: n=3 elseJ.Nawrocki, Rekursja

56 Silnia S: n=1 else S: n=2 else S: n=0 then S: n=3 elseJ.Nawrocki, Rekursja

57 Silnia S: n=0 then S: n=1 else S: n=2 else S: n=3 elseJ.Nawrocki, Rekursja

58 Top Silnia S: n=0 then S: n=1 else S: n=2 else S: n=3 elsefunction S(n: integer):integ begin if n=0 then S:= 1 else S:= S(n-1) * n end; var n: integer; read(n); writeln( S(n) ) end. S: n=1 else S: n=2 else S: n=3 else J.Nawrocki, Rekursja

59 Usuwanie rekursji res res resfunction S(n: integer): integer; begin if n=0 then S:= 1 else S:= S(n-1) * n end; res:= res * i S(i) = res * i res:= 1 S(i) = S(i-1) * i S(0) = 1 S(n)  ..  S(i)  S(i-1)  ..  S(1)  S(0) res res res J.Nawrocki, Rekursja

60 Usuwanie rekursji res res resfunction S(n: integer): integer; begin end; res:= res * i res:= 1 S(n)  ..  S(i)  S(i-1)  ..  S(1)  S(0) res res res J.Nawrocki, Rekursja

61 Usuwanie rekursji res res resfunction S(n: integer): integer; begin res:= 1; (* res:= S(0) *) S:= res end; res:= res * i res:= 1 S(n)  ..  S(i)  S(i-1)  ..  S(1)  S(0) res res res J.Nawrocki, Rekursja

62 Usuwanie rekursji res res resfunction S(n: integer): integer; begin res:= 1; (* res:= S(0) *) S:= res end; res:= res * i res:= 1 i= 1 .. n S(n)  ..  S(i)  S(i-1)  ..  S(1)  S(0) res res res J.Nawrocki, Rekursja

63 Usuwanie rekursji var res,i: integer; res res resfunction S(n: integer): integer; begin res:= 1; (* res:= S(0) *) for i:= 1 to n do res:= res * i; S:= res end; var res,i: integer; res:= res * i res:= 1 i= 1 .. n S(n)  ..  S(i)  S(i-1)  ..  S(1)  S(0) res res res J.Nawrocki, Rekursja

64 Wielomian Plan wykładu Silnia Liczby Fibonacciego Operacja minimumJ.Nawrocki, Rekursja

65 p(x,n) =  ajxn-j = a0xn + a1xn-1 + .. + an-1x1 + anWielomian Schemat Hornera p(x,n) =  ajxn-j = a0xn + a1xn an-1x1 + an p(x, 0) = a0 p(x, n) = p(x, n-1)*x + an p(x, 1) = p(x, 0)*x + a1 = a0*x + a1 p(x, 2) = p(x, 1)*x + a2 = = (p(x, 0)*x + a1)*x + a2 = = (a0*x + a1)*x + a2 = = a0*x2 + a1*x + a2 J.Nawrocki, Rekursja

66 p(x,n) =  ajxn-j = a0xn + a1xn-1 + .. + an-1x1 + anWielomian Schemat Hornera p(x,n) =  ajxn-j = a0xn + a1xn an-1x1 + an p(x, 0) = a0 p(x, n) = p(x, n-1)*x + an J.Nawrocki, Rekursja

67 p(x,n) =  ajxn-j = a0xn + a1xn-1 + .. + an-1x1 + anWielomian Schemat Hornera p(x,n) =  ajxn-j = a0xn + a1xn an-1x1 + an var a: array[0..nMax] of real; function p(x: real; n: integer): real; begin if n=0 then p:= a[0] else p:= p(x, n-1)*x + a[n] end; p(x, n) = a dla n=0 p(x, n) = p(x, n-1)*x + an J.Nawrocki, Rekursja

68 Liczby Fibonacciego Plan wykładu Silnia Wielomian Operacja minimumJ.Nawrocki, Rekursja

69 function f(j: integer): integer; begin if j<=1 then f:= 1 Liczby Fibonacciego Wady rekursji f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) function f(j: integer): integer; begin if j<=1 then f:= 1 else f:= f(j-1) + f(j-2) end; J.Nawrocki, Rekursja

70 Liczby Fibonacciego Wady rekursji f(5)= f(4) + f(3) f(4)= f(3) + f(2)(c) Jerzy Nawrocki Liczby Fibonacciego TPI, Wykład 5 Wady rekursji f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) f(5)= f(4) + f(3) f(4)= f(3) + f(2) f(3)= f(2) + f(1) f(3)= f(2) + f(1) f(2)= f(1) + f(0) f(2)= f(1) + f(0) f(2)= f(1) + f(0) J.Nawrocki, Rekursja Rekursja

71 Usuwanie rekursji f(i) = i = 1 1 f(0) = 1, f(1) = 1(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) J.Nawrocki, Rekursja Rekursja

72 Usuwanie rekursji f(i) = i = 1 1 2 f(2)= f(1) + f(0)(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) f(2)= f(1) + f(0) J.Nawrocki, Rekursja Rekursja

73 Usuwanie rekursji f(i) = i = 1 1 2 3 f(3)= f(2) + f(1)(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 3 f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) f(3)= f(2) + f(1) J.Nawrocki, Rekursja Rekursja

74 Usuwanie rekursji f(i) = i = 1 1 2 3 5 4 f(4)= f(3) + f(2)(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 3 5 4 f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) f(4)= f(3) + f(2) J.Nawrocki, Rekursja Rekursja

75 Usuwanie rekursji f(i) = i = 1 1 2 3 5 4 8 5 f(5)= f(4) + f(3)(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 3 5 4 8 5 f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) f(5)= f(4) + f(3) J.Nawrocki, Rekursja Rekursja

76 Usuwanie rekursji f(i) = i = 1 1 2 3 5 4 8 5 f(0) = 1, f(1) = 1(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 3 5 4 8 5 f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) J.Nawrocki, Rekursja Rekursja

77 Usuwanie rekursji 1 1 2 3 5 8 ... i = 1 2 3 4 5 MaxI(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 fib[i]= 1 1 2 3 5 8 ... i = 1 2 3 4 5 MaxI f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) var fib: [0 .. MaxI] of integer; J.Nawrocki, Rekursja Rekursja

78 Usuwanie rekursji 1 1 2 3 5 8 ... i = 1 2 3 4 5 MaxI(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 fib[i]= 1 1 2 3 5 8 ... i = 1 2 3 4 5 MaxI f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) var fib: [0 .. MaxI] of integer; function f(n: integer): integer; var i: integer; begin fib[0]:= 1; fib[1]:= 1; for i:= 2 to n do fib[i]:= fib[i-1] + fib[i-2]; f:= fib[n] end; J.Nawrocki, Rekursja Rekursja

79 Usuwanie rekursji 1 1 2 3 5 8 ... i = 1 2 3 4 5 MaxI Czy można lepiej?(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 fib[i]= 1 1 2 3 5 8 ... i = 1 2 3 4 5 MaxI f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) var fib: [0 .. MaxI] of integer; function f(n: integer): integer; var i: integer; begin Czy można lepiej? fib[0]:= 1; fib[1]:= 1; for i:= 2 to n do fib[i]:= fib[i-1] + fib[i-2]; f:= fib[n] end; J.Nawrocki, Rekursja Rekursja

80 Usuwanie rekursji f(i) = i = 1 1 2 3 5 4 8 5 f(5)= f(4) + f(3)(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 3 5 4 8 5 f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) f(5)= f(4) + f(3) J.Nawrocki, Rekursja Rekursja

81 Usuwanie rekursji f(i) = i = 1 1 2 3 5 4 8 5 1 2 f(5)= f(4) + f(3)(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 3 5 4 8 5 1 2 f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) f(5)= f(4) + f(3) J.Nawrocki, Rekursja Rekursja

82 Usuwanie rekursji i = 1 1 2 3 5 4 8 5 1 2 a b c(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 3 5 4 8 5 1 2 a b c f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) c = b + a J.Nawrocki, Rekursja Rekursja

83 Usuwanie rekursji i = 1 1 2 3 5 4 8 5 1 2 a b c(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 3 5 4 8 5 1 2 a b c f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) c = b + a c:= b + a; J.Nawrocki, Rekursja Rekursja

84 Usuwanie rekursji i = 1 1 2 3 5 4 8 5 1 2 a b c(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 3 5 4 8 5 1 2 a b c f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) c:= b + a; J.Nawrocki, Rekursja Rekursja

85 Usuwanie rekursji i = 1 1 2 3 5 4 8 5 13 6 1 2 a b c a b c(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 3 5 4 8 5 13 6 1 2 a b c 1 f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) a b c 2 3 begin c:= b + a; a:= b; b:= c end; J.Nawrocki, Rekursja Rekursja

86 Usuwanie rekursji i = 1 1 2 3 5 4 8 5 13 1 2 6 a b c(c) Jerzy Nawrocki Usuwanie rekursji TPI, Wykład 5 f(i) = i = 1 1 2 3 5 4 8 5 13 1 2 6 a b c f(0) = 1, f(1) = 1 f(i+2) = f(i+1) + f(i) function f(n: integer): integer; var a, b, c, i: integer; begin a:= 1; b:= 1; for i:= 1 to n do begin c:= b + a; a:= b; b:= c end; f:= a end; J.Nawrocki, Rekursja Rekursja

87 Operacja minimum Plan wykładu Silnia Wielomian Liczby FibonacciegoJ.Nawrocki, Rekursja

88 Operacja minimum Ujęcie matematycznef(x)= ( y) [ R(x,y) ] Log2(x)= Log2 x Log2(x)=w  2w  x < 2w+1 Log2(x)= najmn. w : x < 2w+1 Log2(x)= ( w) [ x < 2w+1 ] J.Nawrocki, Rekursja

89 Schemat funkcji w PascaluOperacja minimum Schemat funkcji w Pascalu function f(x: integer): integer; var y: integer; begin y:= 0; while not R(x,y) do y:= y + 1 f:= y end; f(x)= ( y) [ R(x,y) ] J.Nawrocki, Rekursja

90 Operacja minimum Funkcja w PascaluLog2(x)= ( w) [ x < 2w+1 ] function f(x: integer): integer; var w: integer; begin w:= 0; while not (x < P(2, w+1)) do w:= w + 1; f:= w end; J.Nawrocki, Rekursja

91 Operacja minimum Funkcja w Pascalufunction f(x: integer): integer; var p,w: integer; begin w:= 0; p:= 2; (* 2^(0+1) = 2 *) while not (x < p) do w:= w + 1; p:= p * 2 end; f:= w Log2(x)= ( w) [ x < 2w+1 ] J.Nawrocki, Rekursja

92 Operacja minimum Minimum efektywne --- nieefektywne ---f(x)= ( y) [ R(x,y) ] x y R(x,y) Minus1(x)= ( y) [ x < y + 2 ] --- efektywne -- Minus1(x)= ( y) [ x = y + 1 ] --- nieefektywne --- J.Nawrocki, Rekursja

93 Instancja a rekord aktywacji Stos rekordów aktywacji Usuwanie rekursji Zakończenie Wreszcie! Koncepcja rekursji Instancja funkcji Instancja a rekord aktywacji Stos rekordów aktywacji Usuwanie rekursji Minimum efektywne J.Nawrocki, Rekursja

94  Literatura A. Grzegorczyk, Logika matematyczna, PWNJ.Nawrocki, Rekursja

95 2. Zbyt wolno czy zbyt szybko? 3. Czy dowiedziałeś się czegoś ważnego? Ocena wykładu 1. Wrażenie ogólne? (1 - 6) 2. Zbyt wolno czy zbyt szybko? 3. Czy dowiedziałeś się czegoś ważnego? 4. Co poprawić i jak? J.Nawrocki, Rekursja