□ Förberedande uppgifter

Här är en rekursiv funktion för utskrift av en lista:

def utskrift(lista):
    if len(lista) > 0:
        print(lista[0])
        utskrift(lista[1:])

1. Provkör funktionen med listan [1,2,3,4,5]
2. Rita Stack Frames (enligt boken kap 5.5 och 5.6 ) för att visa hur rekursionen fungerar.
3. Byt plats på print-satsen och det rekursiva anropet (så att print-satsen hamnar sist i funktionen).
4. Provkör igen
5. Rita Stack Frames och förklara resultatet.

□ Förbättra söt-sur

Det tråkiga med programmet från förra labben är att det bara talar om att det finns en lösning. För att programmet ska kunna skriva ut alla ord på vägen mellan söt och sur måste varje ord kunna peka på sin förälder.För att hålla reda på både ordet och dess förälder inför vi en ParentNode.

class ParentNode:
    def __init__(self, word, parent = None):
        self.word = word
        self.parent = parent

Huvudprogrammet ska skapa ett ParentNode-objekt och lägga in startordet (som word-attribut). Det som sätts in i kön och plockas ut ur kön är nu inte längre ord utan ParentNode. Det betyder att du måste ändra en del i funktionen makechildren från förra labben.

När makechildren finner slutordet ska den skriva ut hela kedjan genom ett anrop writechain(slutordsnod). Metoden writechain() ska skrivas rekursivt, så att man får ut kedjan med slutordet sist.

Om kön töms utan att någon lösning påträffats bör programmet meddela att det är omöjligt. Och när en lösning skrivits ut bör programmet avbryta körningen. Ett sätt att göra det är sys.exit() om man importerar modulen sys. Ett annat sätt är definiera en egen Exception:

class SolutionFound(Exception):
    pass

och göra raise SolutionFound när lösningen hittats.

Betyg

Denna labb kan endast ge betyg E. Du måste lämna in den och redovisa den i tid för att få göra labbarna för högre betyg.

Redovisning

Labben lämnas in indivuellt med "Lämna in uppgift"-knappen högst upp på sidan, och ska redovisas muntligt av bägge gruppmedlemmarna. Skriv gruppmedlemmarnas namn i kommentarsfältet!

Vid redovisningen ska du kunna

• visa upp och redogöra för de förberedande uppgifterna ovan,
• rita och förklara skillnaden i datastrukturen jämfört med förra labben,
• visa hur utskriften av lösningen fungerar med din rekursiva funktion