Recursieve functies

Recursieve functies

Opdracht:

• Tik let rec macht x n = if n = 0 then 1 else x * macht x (n - 1) in.
• Tik dan macht 2 3 in.
• OCaml antwoordt met - : int = 8. Je kan een functie toepassen in haar eigen lichaam, op voorwaarde dat je de let rec-opdracht gebruikt in plaats van de let-opdracht. Zo'n functie noemen we een recursieve functie.

Je kan de evaluatie van deze functie begrijpen als volgt:

macht 2 3
= if 3 = 0 then 1 else 2 * macht 2 (3 - 1)                       (definitie van macht)
= 2 * macht 2 2                                                  (vereenvoudiging)
= 2 * (if 2 = 0 then 1 else 2 * macht 2 (2 - 1))                 (definitie van macht)
= 2 * (2 * macht 2 1)                                            (vereenvoudiging)
= 2 * (2 * (if 1 = 0 then 1 else 2 * macht 2 (1 - 1)))           (definitie van macht)
= 2 * (2 * (2 * macht 2 0))                                      (vereenvoudiging)
= 2 * (2 * (2 * (if 0 = 0 then 1 else 2 * macht 2 (0 - 1))))     (definitie van macht)
= 2 * (2 * (2 * 1))                                              (vereenvoudiging)
= 8                                                              (vereenvoudiging)

Opdracht:

• Tik let sterren_0 = "" in.
• OCaml antwoordt met sterren_0 : string = "".
• Tik let sterren_1 = "*" ^ sterren_0 in.
• OCaml antwoordt met sterren_1 : string = "*".
• Tik let sterren_2 = "*" ^ sterren_1 in.
• OCaml antwoordt met sterren_2 : string = "**".
• Tik let sterren_3 = "*" ^ sterren_2 in.
• OCaml antwoordt met sterren_3 : string = "***".

Oefening:

• Definieer de functie sterren zodanig dat sterren 3 evalueert tot "***" en sterren 5 evalueert tot "*****".

Oefening:

• Definieer de functie maal die, gegeven twee niet-negatieve gehele getallen, het product van deze getallen berekent. Je mag hierbij enkel de volgende bewerkingstekens gebruiken: =, +, en - (dus NIET *!).

Oefening:

• Definieer de functie ggd die, gegeven twee positieve gehele getallen, de grootste gemene deler van deze twee getallen berekent. Gebruik hiervoor het algoritme van Euclides.