Rekursjon

Læringsmål:

• PLACEHOLDER

Pensum:

• PLACEHOLDER

a)

Fibonaccitalene er definert som følger:

For eksempel er f₃ = f₁ + f₂ = 1 + 1 = 2. Dermed blir begynnelsen av rekken slik: 1, 1, 2, 3, 5, 8, 13, 21... Lag den rekursive funksjonen fibonacci som tar tallet n som parameter og returnerer det n-te elementet i fibonacci-følgen.

b)

Lag en ny funksjon fibStore. Denne skal be om antall ledd og filnavn. Deretter skal den kalle på en rekursiv fibonacci-funksjon som ikke returnerer det n-te leddet, men en liste med alle leddene. a-oppgaven må altså endres litt på.

c)

Lag funksjonen factorial som tar tallet n som parameter og returnerer resultatet av den matematiske operasjonen n!. Funksjonen er denert slik:

d)

Lag funksjonen des2bin(descimal) som tar inn et positivt heltall (eller 0) og returnerer den binære representasjonen av tallet som en tekststreng. Funksjonen skal være rekursiv, og for hvert rekursive kall skal funksjonen nne det binære sieret lengst til høyre i resultatet. Funksjonen kan implementeres etter følgende rekursjonsskjema:

Test funksjonen slik:

des2bin (0) 	% '0'
des2bin (1) 	% '1'
des2bin (2) 	% '10'
des2bin (127) 	% '1111111 '

d)

Lag funksjonen tower_of_hanoi(n, source, dest, temp). Funksjonen skal skrive ut løsningen på Tower of Hanoi problemet. Se wikipedia for denisjon av problemet. Eksempelutskrift for tower_of_hanoi(3, 1, 3, 2) er:

Flytt fra 1 til 3
Flytt fra 1 til 2
Flytt fra 3 til 2
Flytt fra 1 til 3
Flytt fra 2 til 1
Flytt fra 2 til 3
Flytt fra 1 til 3