Задатак 1.
Израчунати вредност
f
2
(
2
,
2
)
аритметичке функције
f
2
(
x , y
)=
x
⋅
y
(
f
2
(
x ,
0
)=
0
)
,
уколико претпоставимо да је дата аритметичка функција
f
1
(
x , y
)=
x
+
y
(при
рачунању вредности користити рекурзиван запис за функцију
f
2
(
x , y
)
).
Решење:
За решавање овог задатка користићемо рекурзију (основну, стандардну) као
врсту рекурзивне функције. Да видимо шта каже дефиниција рекурзије:
Рекурзија.
Нека су дате функције
g
=
g
(
x
1
,x
2
,
...
, x
n
)
:
N
n
→
N ,
h
=
h
(
x
1
, x
2
,
...
, x
n
, y , z
)
:
N
n
+
2
→
N
.
Тада (стандардна) рекурзија функција g и h јесте функција
f
=
rec
(
g ,h
)
:
N
n
+
1
→
N
дефинисана са
f
(
x
1
,
...
, x
n
, y
)=
{
g
(
x
1
,
...
, x
n
)
:
y
=
0
,
h
(
x
1
,
...
,x
n
, y
−
1
, f
(
x
1
,
...
, x
n
, y
−
1
))
:
y
≠
0.
У нашем примеру можемо лако видети да је n = 1, јер имамо само једну
променљиву x. Одавде закључујемо да је функција g функција облика
g
=
g
(
x
)
:
N
1
→
N ,
а функција h функција облика
h
=
h
(
x , y
−
1
, f
(
x , y
−
1
))
:
N
3
→
N
.
Разматрамо 2 случаја. Први случај је када је y = 0, где тражимо функцију g, а
други случај је када је
y
≠
0
, где тражимо функцију h. Функцију f
2
(x,y) можемо
компактније записати као:
f
2
(
x , y
)=
{
0:
y
=
0
,
x
⋅
y
:
y
≠
0.
На располагању нам стоје 3 основне полазне функције, а то су: нула функција
(N(x) = 0), функција следбеник (S(x) = x + 1) и функција пројекције (
U
i
n
(
x
1
, x
2
,
...
, x
i
,
...
,x
n
)=
x
i
). Помоћу ових основних функција, ми ћемо моћи да
полазну функцију сведемо на одговарајући облик који ће нам помоћи да
нађемо функције g и h.
y
=
0:
g
(
x
)=
f
2
(
x , y
)=
f
2
(
x ,
0
)=
x
⋅
0
=
0
=
N
(
x
)
⇒
g
=
N
y
≠
0:
f
2
(
x , y
)=
x
⋅
y
Пошто функцију h треба да сведемо на облик који је горе наведен, видимо да
нам треба y – 1. То можемо „направити“ тако што ћемо следећи облик функције
f
2
(x,y) написати:
f
2
(
x , y
)=
x
⋅
(
y
−
1
)
+
x
.
Пошто имамо на располагању и функцију
f
1
(
x , y
)=
x
+
y
, која је дата у тексту
задатка, ми нашу функцију f
2
(x,y) можемо написати:
f
2
(
x , y
)=
f
1
(
x
⋅(
y
−
1
)
, x
)=
f
1
(
f
2
(
x , y
−
1
)
,x
)
.
Да бисмо одредили функцију h, која нам треба, ми видимо да нам у претходној
формули недостаје y – 1. Овде сада може да нам послужи функција пројекције, и
претходну формулу можемо да сведемо на облик:
f
1
(
f
2
(
x , y
−
1
)
, x
)=
f
1
(
U
3
3
(
x , y
−
1
, f
2
(
x , y
−
1
))
,U
1
3
(
x , y
−
1
, f
2
(
x , y
−
1
)))=
=
f
1
(
U
3
3
,U
1
3
)(
x , y
−
1
, f
2
(
x , y
−
1
))
⇒
h
=
f
1
(
U
3
3
,U
1
3
)
.
Одавде је очигледно h. Можемо приметити да се израз y – 1 нигде не користи,
али нам је био потребан да бисмо нашли функцију h, уз помоћ функције
пројекције. Коначан израз за рекурзију (основну) биће:
f
2
=
rec
(
N , f
1
(
U
3
3
,U
1
3
))
.
