Göm menyn

Dubbelrekursion

Vi har tidigare skrivit funktioner som med hjälp av iteration eller rekursion bearbetat alla element i en sträng eller en lista. Listor är mer generella än strängar och kan innehålla i princip vad som helst, t.ex. andra listor. Om vi vill behandla alla element i den typen av mer komplicerade strukturer är det i princip enbart rekursion som gäller om man ska lösa det generellt. När vi bearbetar "listor i listor" kallas det för dubbelrekursion.

Beräkna den totala längden i en nästlad lista

Vi ska nu skriva en funktion som använder sig av dubbelrekursion för att beräkna den totala längden av en lista och dess underlistor.

Nästlade listor

Skillnaden mot hur vi har gjort rekursion tidigare är att nu kollar vi även om det första elementet i listan är en lista, i så fall anropar vi funktionen på både den underlistan och listan med resten av elementen.

Vad händer egentligen i programmet när vi kör det? Här är ser vi ordningen som anropen sker i när vi anropar len2([1, 'two', [3, 4, 'five'], [True]]).

Alt text

Exempel

Vi vill ha en funktion remove som kan ta bort alla förekomster av ett element ur en lista. Listan kan innehålla underlistor, och dessa ska också gås igenom. Lösningen ska egentligen bygga upp en ny lista utan förekomsterna av det givna elementet, snarare än att plocka bort från den befintliga listan.

Vi tänker oss i första hand en rekursiv lösning och gör följande fallanalys. Hur kan man tänka sig att olika listor börjar och hur ska vi behandla dem?

Första elementet i listan Behandling
Tom lista Returnera tom lista
Underlista Bearbeta underlistan och resten
Elementet vi ska ta bort Fortsätt med resten
Element som ska vara kvar Bygg ihop och fortsätt med resten

Rekursiv lösning

Iterativ lösning

Observera att lösningen inte är helt iterativ. Det är väldigt svårt att få till en helt iterativ lösning som klarar av godtyckligt djupa strukturer.


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2016-08-15