Recursie: oefeningen

Je vind tests en skelet-code voor de oefeningen rond recursie op Github:

https://github.com/KULeuven-Diepenbeek/ses-deel2-oefeningen-05-recursie.git

Palindroom

Schrijf een recursieve functie isPalindrome die nagaat of een String een palindroom is. Een String is een palindroom als die hetzelfde is van links naar rechts als van rechts naar links, bijvoorbeeld

  • racecar
  • level
  • deified
  • lepel
  • droomoord
  • redder
  • meetsysteem
  • koortsmeetsysteemstrook

String omkeren

Schrijf een recursieve methode reverse om een String om te keren, bijvoorbeeld:

  • Hello -> olleH
  • racecar -> racecar

Element zoeken in lijst

Schrijf een recursieve functie <T> int search(List<T> list, T element) die nagaat of het gegeven element voorkomt in de gegeven lijst. Als het element voorkomt, wordt de index teruggegeven, anders -1.

  • Maak eerst een versie die werkt voor een willekeurige (niet-gesorteerde) lijst.
  • Maar vervolgens een snellere versie die werkt voor een gesorteerde lijst, door het te doorzoeken stuk van de lijst telkens halveert en slechts in één van die helften verder gaat zoeken. (Dit is ‘binary search’)

Duplicaten verwijderen

Schrijf een recursieve methode removeDuplicateCharacters die opeenvolgende dezelfde karakters uit een String verwijdert. Bijvoorbeeld:

  • aaaaa -> a
  • koortsmeetsysteemstrook -> kortsmetsystemstrok
  • AAAbbCdddAAA -> AbCdA

Trap beklimmen

Schrijf een functie om te berekenen hoeveel verschillende manieren er zijn om een trap met \( n \) treden op te gaan, als je bij elke stap kan kiezen om 1 of 2 treden tegelijk te nemen. Bijvoorbeeld, een trap met \( n = 4 \) treden kan je op 5 verschillende manieren beklimmen:

  1. 1 trede, 1 trede, 1 trede, 1 trede
  2. 1 trede, 1 trede, 2 treden
  3. 1 trede, 2 treden, 1 trede
  4. 2 treden, 1 trede, 1 trede
  5. 2 treden, 2 treden

Alle permutaties van een lijst berekenen

Schrijf een functie allPermutations die een Set teruggeeft met alle permutaties van een gegeven lijst. Bijvoorbeeld:

  • allPermutations(List.of("A", "B")) = [ [A, B], [B, A] ]
  • allPermutations(List.of("A", "B", "C")) = [ [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A] ]

Gepast betalen

Schrijf een recursieve methode boolean kanGepastBetalen(int bedrag, List<Integer> munten) die nagaat of je het gegeven bedrag (uitgedrukt in eurocent) gepast kan betalen met (een deel van) de gegeven munten (en briefjes). Elke munt in de lijst mag slechts één keer gebruikt worden. Bijvoorbeeld:

  • kanGepastBetalen(20, List.of(50, 10, 10, 5)) geeft true terug, want 10+10 = 20.
  • kanGepastBetalen(125, List.of(100, 100, 50, 20, 10, 5 )) geeft true terug, want 100+20+5 = 125.
  • kanGepastBetalen(260, List.of(100, 100, 50, 20, 5 )) geeft false terug: er is geen combinatie van munten die samen 260 geeft.

Gepast betalen (bis)

Gegeven een lijst van muntwaarden (bv. 5, 10, 20, 50, 100, 200), schrijf een recursieve methode int countChange(int amount, List<Integer> coinValues) die bepaal op hoeveel manieren je een specifiek bedrag kan betalen. Je mag nu veronderstellen dat je een voldoende aantal (of oneindig veel) munten van elke opgegeven waarde hebt. Met andere woorden, je mag een munt(waarde) meerdere keren gebruiken.

Bijvoorbeeld, met bovenstaande muntwaarden

  • countChange(35, List.of(5, 10, 20, 50, 100, 200)) == 6: je kan een bedrag van 35 betalen op 6 manieren:
    • 7×5
    • 1×10 en 5×5
    • 1×10 en 1×20 en 1×5
    • 2×10 en 3×5
    • 3×10 en 1×5
    • 1×20 en 3×5
  • countChange(260, List.of(5, 10, 20, 50, 100, 200)) == 646: je kan een bedrag van 260 betalen op 646 manieren
  • countChange(1000, List.of(5, 10, 20, 50, 100, 200)) == 98411: je kan een bedrag van 1000 betalen op 98411 manieren

Alle prefixen van een String

Schrijf een recursieve functie allPrefixes die een Set teruggeeft met alle prefixen van een gegeven String. Bijvoorbeeld:

  • allPrefixes("cat") == { "", "c", "ca", "cat" }
  • allPrefixes("Hello") == { "", "H", "He", "Hel", "Hell", "Hello" }

Alle interleavings van twee strings

Schrijf een recursieve functie allInterleavings(String s1, String s2) die een Set teruggeeft met alle interleavings van de twee strings s1 en s2. Een interleaving is een nieuwe string met daarin alle karakters van de eerste en de tweede string, in dezelfde volgorde waarin ze in elk van de originele strings voorkomen, maar mogelijk afwisselend. Bijvoorbeeld:

  • allInterleavings("A", "B") = [AB, BA]
  • allInterleavings("ABC", "x") = [ABCx, ABxC, AxBC, xABC]
  • allInterleavings("AB", "xy") = [ABxy, AxBy, AxyB, xABy, xAyB, xyAB]
  • allInterleavings("ABC", "xy") = [ABCxy, ABxCy, ABxyC, AxBCy, AxByC, AxyBC, xABCy, xAByC, xAyBC, xyABC]

Sum of digits

Schrijf een recursieve methode int sumOfDigits(long number) die de som van de cijfers van een (niet-negatief) getal berekent, en dat herhaalt tot die som kleiner is dan 10. Bijvoorbeeld: 62984 geeft 6+2+9+8+4 = 29; dat wordt vervolgens 2+9 = 11; en dat wordt uiteindelijk 1+1 = 2. Het resultaat is dus 2.

Vliegtuigreis

Gegeven een record Item:

record Item(String name, int weight, int value) {}

wat een item voorstelt dat je mee wil nemen op reis. Het item heeft een naam, een gewicht (> 0), en een waarde (hoe graag je het mee wil, > 0).

Schrijf een methode List<Item> pack(List<Item> choices, int maxWeight) die een keuze maakt uit de gegeven lijst van items, zodanig dat de items met een zo groot mogelijke totaalwaarde kan meenemen zonder dat het totale gewicht hoger wordt dan het maximumgewicht (opgelegd door de vliegtuigmaatschappij).

Bijvoorbeeld, met vier items (A, 50kg, 10), (B, 20kg, 5), (C, 10kg, 2), en (D, 5kg, 1):

  • met een totaal toegelaten gewicht van 100kg kan je alle items meenemen, voor een totale waarde van 18;
  • met een totaal toegelaten gewicht van 60kg kan je best items A en C meenemen, voor een totale waarde van 12;
  • met een totaal toegelaten gewicht van 20kg kan je best item B meenemen, voor een totale waarde van 5;

Powerset

Schrijf een recursieve functie Set<Set<T>> powerset(Set<T> s) die de powerset berekent van de gegeven set s. De powerset is de set van alle deelverzamelingen van s. Bijvoorbeeld:

  • powerset(Set.of("A", "B")) = [[], [A], [B], [A, B]]
  • powerset(Set.of("A", "B", "C")) = [[], [A], [B], [C], [A, B], [A, C], [B, C], [A, B, C]]

Gebalanceerde haakjes

Schrijf met behulp van recursie een methode boolean balancedParentheses(String s) die nagaat of alle haakjes in de gegeven string gebalanceerd zijn. Bijvoorbeeld:

  • () geeft true terug
  • ()) geeft false terug
  • ()() geeft true terug
  • )( geeft false terug
  • (( geeft false terug
  • abc(def(xy))z geeft true terug
  • a(bc(def(xy))z geeft false terug
Hint

Je eerste intuïtie, namelijk ‘is deze string gebalanceerd’ als deelprobleem voor kleinere strings gebruiken, zal je niet verder helpen. Probeer een andere (gerelateerde) vraag te vinden die wél nuttig kan zijn om het probleem recursief op te lossen. Gebruik ook het worker-wrapper-patroon.

Longest common subsequence

Schrijf een recursieve methode String longestCommonSubsequence(String s1, String s2) die de langste reeks karakters teruggeeft die in beide strings in dezelfde volgorde terugkomen (niet noodzakelijk aaneensluitend). Als er meerdere oplossingen zijn, maakt het niet uit welke je teruggeeft.

Bijvoorbeeld:

  • longestCommonSubsequence("gitaarsnaar", "imaginair") == "ginar" of "ianar":

    gitaarsnaar
    en
    imaginair
    , of
    gitaarsnaar
    en
    imaginair

  • longestCommonSubsequence("aardappel", "adoptie") == "adpe":

    aardappel
    en
    adoptie

  • longestCommonSubsequence("sterrenstelselsamenstellingsanalyseinstrument", "restaurantkeukenapparatuurontwerpmethodiek") == "restantenaantrmet" (met dank aan ChatGPT voor de suggestie):

    sterrenstelselsamenstellingsanalyseinstrument
    en
    restaurantkeukenapparatuurontwerpmethodiek

Het laatste voorbeeld zal waarschijnlijk veel te lang duren. Je kan nadenken of je je algoritme wat ‘slimmer’ kan maken.

Stack omkeren

Schrijf een recursieve methode <T> void reverse(Deque<T> stack) die de volgorde van de items in een stack (Deque) omdraait, zonder gebruik te maken van een extra datastructuur (dus zonder een andere array, lijst, set, …). Maak enkel gebruik van de isEmpty()-, pollFirst() en addFirst()-methodes van de Deque-interface.

var stack = new LinkedList<>(List.of("A", "B", "C", "D", "E", "F"));
System.out.println(stack); // [A, B, C, D, E, F]
reverse(stack);
System.out.println(stack); // [F, E, D, C, B, A]
Hint

Zou een (recursieve) hulpoperatie om een element onderaan de stack in te voegen nuttig kunnen zijn?

Denkvraag: ondanks dat je geen extra datastructuur mag gebruiken in je oplossing, wordt er toch een vorm van extra opslag gebruikt om de stack te kunnen omkeren. Waar bevindt die opslag zich?

Toren van Hanoi (uitbreiding)

Los de toren van Hanoi op voor \( n\) schijven op 4 stapels (dus 2 hulpstapels). Je kan je oplossing manueel uittesten via deze simulator. (In de simulator moet je klikken, niet slepen)

Sorteren van een lijst

Schrijf een recursieve methode om een lijst van getallen te sorteren. De sortering moet in-place gebeuren (je past de lijst zelf aan door elementen van volgorde te wisselen, en geeft dus geen nieuwe lijst terug).

reduce

Schrijf een recursieve reduce-operatie die werkt op een lijst, naar analogie met de reduce-operatie op streams.

List<Integer> lst = List.of(1, 2, 3, 4);
int sum = reduce(lst, 0, (sum, x) -> sum + y); // sum == 10

Boomstructuur

In deze oefening maken we gebruik van een boomstructuur. Deze structuur zal in het vak rond algoritmen en datastructuren een belangrijke rol spelen en daar dan ook uitgebreid aan bod komen. We gebruiken deze hier enkel als voorbeeld.

Gegeven onderstaande record om een boomstructuur op te bouwen:

public record TreeNode<T>(T value, TreeNode<T> left, TreeNode<T> right){}

De boom

CBDAFE

kan je hiermee aanmaken als:

var tree = new TreeNode<>("A",
              new TreeNode<>("B",
                new TreeNode<>("C", null, null),
                new TreeNode<>("D", null, null)),
              new TreeNode<>("E",
                new TreeNode<>("F", null, null),
                null));
  1. Schrijf een recursieve methode int treeSize(TreeNode<?> tree) om het totale aantal knopen in de boom te berekenen. Voor de boom hierboven is de grootte 6.
  2. Schrijf een recursieve methode int treeHeight(TreeNode<?> tree) om de hoogte van de boom te berekenen. De hoogte is het maximum aantal stappen van de wortel (“A” hierboven) tot een kind (“C”, “D”, of “F”). In het voorbeeld is de hoogte dus 2.
  3. Schrijf een recursieve methode <T> void visitDepthFirstPreOrder(TreeNode<T> tree, Consumer<T> consumer) die de elementen van de boom overloopt in depth-first, pre-order volgorde. Dat houdt in: eerst de huidige knoop, dan de knopen van de linkertak (opnieuw in depth-first pre-order volgorde) en daarna die van de rechtertak. Voor de boom hierboven worden dus achtereenvolgens knopen “A”, “B”, “C”, “D”, “E”, en “F” bezocht en doorgegeven aan de consumer. Een voorbeeld van het gebruik van de methode om de knopen uit te printen:
    visitDepthFirstPreOrder(tree, System.out::print);
System.out.println();
  4. Schrijf een recursieve methode <T> void visitDepthFirstInOrder(TreeNode<T> tree, Consumer<T> consumer) die de elementen van de boom overloopt in depth-first, in-order volgorde. Dat houdt in: eerst de linkertak (in depth-first in-order volgorde), dan de knoop zelf, dan de rechtertak. Voor de boom hierboven worden dus achtereenvolgens knopen “C”, “B”, “D”, “A”, “F”, en “E” bezocht en doorgegeven aan de consumer.
  5. Schrijf een recursieve methode <T> TreeNode<T> mirrorTree(TreeNode<T> tree) om een willekeurige boom te spiegelen: het resultaat moet een nieuwe boom zijn, waar de linker-takken de rechtertakken geworden zijn en omgekeerd. De gespiegelde versie van de boom hierboven is dus:
EFADBC
  1. (extra) Schrijf een methode String prettyPrint(TreeNode<?> tree) die een ASCII-voorstelling van de boom maakt. De voorbeeldboom wordt bijvoorbeeld:
    A
|
+-- B
|   |
|   +-- C
|   '-- D
'-- E
    |
    +-- F

Expressie (uit records)

De oefeningen over de expressie-hierarchie uit de les rond records maken ook gebruik van recursie.