Tentamen: rekursjon teknikker

Dette settet med flashcards dekker viktige begreper innen rekursjonsteknikker i programmering, designet for universitetsstudenter som ønsker å forstå og anvende disse konseptene effektivt.

Henrik2008·56 flashkort·56 spørsmål
universitetcomputer_scienceprogramming
0
Kjent
1 / 56
0
Lærer
Forside

Hva er rekursjon?

Trykk for å vende
Bakside

Rekursjon er en programvareteknikk der en funksjon kaller seg selv for å løse et problem.

Trykk for å vende
Skjønner
Lærer fortsatt

Quiz(56 spørsmål)

Spørsmål 1 av 56

1. Hva er hovedformålet med rekursjon?

Begreper i dette studiesettet(56)

Grunnleggende rekursjon(16)

Hva er rekursjon?

Rekursjon er en programvareteknikk der en funksjon kaller seg selv for å løse et problem.

Definer basis tilfelle.

Basis tilfelle er det enkleste tilfellet i rekursjon som stopper den rekursive prosessen.

Hvorfor bruke rekursjon?

Rekursjon forenkler koden, gjør den mer lesbar og er nyttig for problemer med naturlig deling.

Fyll inn: Rekursjon er en _____ teknikk.

Selvrefererende

Sann eller usann: Rekursjon krever alltid mer minne enn iterasjon.

Usann. I noen tilfeller kan rekursjon være mer minneeffektiv.

Gi et eksempel på et rekursivt problem.

Fibonacci-sekvensen: F(n)=F(n−1)+F(n−2)\displaystyle F(n) = F(n-1) + F(n-2) med basis tilfeller F(0)=0\displaystyle F(0)=0, F(1)=1\displaystyle F(1)=1.

Hva er et rekursivt kall?

Et rekursivt kall skjer når en funksjon kaller seg selv med et annerledes argument.

Sammenlign rekursjon og iterasjon.

Rekursjon bruker funksjonskall, mens iterasjon bruker løkker. Begge kan oppnå samme resultat.

Definer rekursiv funksjon.

En funksjon er rekursiv når den inkluderer en eller flere selvrefererende anrop.

Hva er en rekursiv dybde?

Rekursiv dybde er antallet nivåer med funksjonskall i rekursjon før basis tilfelle nås.

Hva skjer uten basis tilfelle?

Uten basis tilfelle vil rekursjonen fortsette uendelig og føre til en stabeloverløp.

Beskriv hvordan rekursjon fungerer.

Rekursjon fungerer ved å dele opp problemet i enklere underproblemer som deretter løses.

Sann eller usann: Rekursjon kan alltid erstattes med løkker.

Sann. Enhver rekursiv løsning kan implementeres med iterasjon, men koden kan bli mer kompleks.

Hva er en rekursiv løsning for faktorial?

Faktorial av n kan defineres som n!=n∗(n−1)!\displaystyle n! = n * (n-1)! med 0!=1\displaystyle 0! = 1.

Nevn en ulempe med rekursjon.

Rekursjon kan føre til høy minnebruk på grunn av stabelen av funksjonskall.

Hva er tail rekursjon?

Tail rekursjon er når den rekursive funksjonen returnerer resultatet direkte fra det siste rekursive kallet.

Rekursjonstyper(12)

Direkte rekursjon

En funksjon som kaller seg selv direkte. Eksempel: Fibonacci-funksjonen.

Indirekte rekursjon

En funksjon som kaller en annen funksjon, som igjen kaller den første.

Eksempel på direkte rekursjon

Fibonacci-serien: F(n)=F(n−1)+F(n−2)\displaystyle F(n) = F(n-1) + F(n-2).

Indirekte rekursjon eksempler

Funksjoner A og B, der A kaller B og B kaller A.

Rekursiv funksjon

En funksjon som løser et problem ved å dele det opp i mindre delproblemer.

Sett inn det riktige begrepet: Rekursjon kan være __________ eller __________.

direkte, indirekte.

Når brukes direkte rekursjon?

Når delproblemet er en direkte forenkling av originalproblemet.

Når brukes indirekte rekursjon?

Når en oppgave kan dele seg mellom flere funksjoner.

Sann eller usann: Indirekte rekursjon er mer effektiv enn direkte rekursjon.

Usann. Effektiviteten avhenger av problemet.

Sammenlign rettlinjet og rekursiv tilnærming.

Rettlinjet: Iterativ. Rekursiv: Deler opp i delproblemer.

Hva er en base case?

Den enkleste versjonen av et problem; stopper rekursjonen.

Effekten av rekursjon på minnebruk?

Rekursjon kan føre til høy minnebruk pga. stakkoverløp.

Rekursjon og algoritmer(14)

Rekursjon

En teknikk der en funksjon kaller seg selv for å løse et problem.

Hvordan brukes rekursjon i algoritmer?

For å bryte ned komplekse problemer til enklere delproblemer som kan løses gjentatte ganger.

Sann eller usann: Rekursjon er alltid mer effektivt enn iterasjon.

Usann. Rekursjon kan være mindre effektivt på grunn av funksjonskalloverhead.

Eksempel på rekursiv funksjon

Fibonacci-serien: F(n)=F(n−1)+F(n−2)\displaystyle F(n) = F(n-1) + F(n-2) for n>1\displaystyle n > 1.

Hva er en basecase?

Det er betingelsen som stopper rekursjonen og forhindrer uendelig kall.

Rekursiv vs. iterativ løsning

Rekursiv: Bruker funksjonskall. Iterativ: Bruker løkker.

Hvorfor bruke rekursjon?

Rekursjon forenkler koden og gjør komplekse algoritmer mer lesbare.

Fill in the blank: Rekursjon er spesielt nyttig for _______.

problemer som kan deles opp i mindre, like problemer.

Trinn i rekursjon

- Definer problemet - Bestem basecase - Kall funksjonen på delproblemer

Sann eller usann: Rekursjon kan føre til stack overflow.

Sann. For mange rekursive kall kan overskride minnet i stakken.

Algoritmisk tenkning

Evnen til å løse problemer ved å utvikle trinnvise løsninger.

Rekursjonens kompleksitet

Tid og plasskompleksitet avhenger av antall rekursive kall og dybde av stakk.

Hva er en rekursiv algoritme?

En algoritme som løser et problem ved å dele det opp og bruke seg selv.

Eksempel på praktisk bruk av rekursjon

Søk i trær, for eksempel dybde-først søk (DFS).

Effektivitet og optimalisering(14)

Hva er tidskompleksitet?

Tidskompleksitet beskriver hvor mye tid en algoritme bruker i forhold til størrelsen på input. Vanlige betegnelser inkluderer O(1), O(n) og O(n²).

Definer plasskompleksitet.

Plasskompleksitet beskriver hvor mye minne en algoritme bruker i forhold til størrelsen på input. For eksempel, O(n) betyr at plassen vokser lineært med inputstørrelsen.

Sann eller usann: Rekursive funksjoner bruker alltid mindre plass.

Usann. Rekursive funksjoner kan bruke mer plass på grunn av kallstakken, spesielt med dype rekursive kall.

Sammenlign iterasjon og rekursjon.

Iterasjon bruker løkker for å gjenta handlinger, mens rekursjon bruker funksjonskall for å oppnå gjentakelse.

Fyll inn: Tidskompleksiteten til Fibonacci-rekursjon er ______.

O(2^n) - Dette er fordi den rekursive løsningen for Fibonacci genererer mange gjentatte beregninger.

Hva er memoization?

Memoization er en teknikk for å optimalisere rekursive algoritmer ved å lagre allerede beregnede resultater for å unngå gjentatt arbeid.

Årsak → Effekt: Dyp rekursjon kan føre til ______.

Stack overflow - Når rekursjonen går dypere enn minnebegrensningene for programmet.

Eksempel: Tidskompleksitet for binært søk?

O(log n) - Fordi søket halverer inputstørrelsen hver gang.

Hva er hovedproblemet med naiv rekursjon?

Den kan ha høy tidskompleksitet og ineffektiv minnebruk, som i tilfellet med Fibonacci-tall.

Sann eller usann: Rekursjon er alltid mer effektiv enn iterasjon.

Usann. Rekursjon kan være mindre effektivt på grunn av overhead for funksjonskall.

Beskriv tail rekursjon.

Tail rekursjon skjer når det rekursive anropet er den siste handlingen i funksjonen, noe som kan optimaliseres av kompilatoren.

Fyll inn: Den optimale rekursive strategien for å løse et problem er ______.

Dynamisk programmering - Det kombinerer rekursjon med lagring av delresultater.

Sammenlign rekursjon og dynamisk programmering.

Rekursjon er ofte enklere å implementere, mens dynamisk programmering gir bedre ytelse via lagring av resultater.

Hva påvirker effektiviteten til rekursive funksjoner?

Antall rekursive kall, dybden av rekursjonen, og hvor mye arbeid som gjøres i hvert kall.

Spørsmål i dette studiesettet(56)

1. Hva er hovedformålet med rekursjon?

A.Å forenkle løsningen på et problem ved å dele det opp i mindre deler.
B.Å gjøre koden mer kompleks.
C.Å unngå bruk av minne.
D.Å redusere hastigheten på programmet.

2. Hva kalles en funksjon som kaller seg selv direkte for å løse et problem?

A.Direkte rekursjon
B.Indirekte rekursjon
C.Iterativ funksjon
D.Base case

3. Hva er definisjonen på rekursjon?

A.En teknikk der en funksjon kaller seg selv.
B.En metode for å iterere over en liste.
C.En algoritme for sortering av data.
D.En tilnærming for å løse problemer enkelt.

4. Hva beskriver tidskompleksitet?

A.Hvor mye tid en algoritme bruker i forhold til størrelsen på input.
B.Hvor mye minne en algoritme bruker i forhold til størrelsen på input.
C.Hvor mange funksjonskall en rekursiv funksjon gjør.
D.Hvor mye data som blir behandlet av en algoritme.

5. Hva er en viktig egenskap ved basis tilfelle i rekursjon?

A.Det må ha en løsning som er kjent og enkel.
B.Det må være det mest komplekse tilfellet.
C.Det må alltid ha samme verdi.
D.Det må alltid være det første tilfellet i rekursjonen.

6. Hvilket alternativ beskriver best hva indirekte rekursjon er?

A.En funksjon som kaller seg selv
B.En funksjon som kaller en annen funksjon som igjen kaller den første
C.En funksjon uten rekursjon
D.En lineær algoritme

7. Hvordan kan rekursjon være nyttig i algoritmer?

A.Ved å forenkle komplekse problemer til delproblemer.
B.Ved å redusere kjøretiden betydelig.
C.Ved å unngå bruk av minne.
D.Ved å forbedre sikkerheten i koden.

8. Hvilken av følgende beskriver plasskompleksitet?

A.Hvor mye minne en algoritme bruker i forhold til størrelsen på input.
B.Hvor raskt en algoritme kan fullføre.
C.Antall iterasjoner som trengs for å fullføre et sett med data.
D.Kostnaden ved å lagre data i minnet.

9. Hva skjer hvis et rekursivt kall ikke når basis tilfelle?

A.Programmet terminerer normalt.
B.Det vil føre til en stabeloverløp.
C.Det vil gå raskere.
D.Det vil gi en feil i koden.

10. Hvilket av følgende eksempler er typisk for direkte rekursjon?

A.Fibonacci-serien
B.To funksjoner som kaller hverandre
C.En enkel løkke
D.Databasesøk

11. Sann eller usann: Rekursjon kan alltid brukes i stedet for iterasjon.

A.Usann.
B.Sann.
C.Usann kun for store datamengder.
D.Sann kun for matematiske problemer.

12. Sann eller usann: Rekursive funksjoner krever alltid mer minne enn iterative funksjoner.

A.Usann
B.Sann
C.Avhenger av implementeringen
D.Bare i tilfelle dyp rekursjon

13. Hvilket av følgende er et korrekt eksempel på rekursjon?

A.Summen av de første n naturlige tallene.
B.En for-løkke som addere tall.
C.En array-søk med binær søk.
D.En funksjon som kaller seg selv for å beregne Fibonacci-tall.

14. Når er direkte rekursjon vanligvis mest hensiktsmessig å bruke?

A.Når oppgaven kan deles mellom flere funksjoner
B.Når delproblemet er en direkte forenkling av originalproblemet
C.Når det er stor datamengde
D.Når hastighet er kritisk

15. Hva er et eksempel på en rekursiv funksjon?

A.Fibonacci-serien.
B.Bubble sort.
C.Binærsøk.
D.En enkel løkke.

16. Hva er et kjennetegn ved tail rekursjon?

A.Det rekursive anropet skjer som den siste handlingen i funksjonen.
B.Det bruker mer minne enn vanlig rekursjon.
C.Det kan ikke optimaliseres av kompilatoren.
D.Det krever flere rekursive kall enn vanlig rekursjon.

17. Hva er en fordel med rekursjon over iterasjon?

A.Rekursjon kan være mer intuitiv for enkelte problemer.
B.Rekursjon bruker alltid mindre minne.
C.Rekursjon er alltid raskere.
D.Rekursjon krever ikke en programmeringsspråk med støtte for funksjoner.

18. Hvilket utsagn er usant om indirekte rekursjon?

A.Det krever mer minne enn direkte rekursjon
B.Det involverer to eller flere funksjoner
C.Det kan forbedre ytelsen for alle problemer
D.Det er en form for rekursjon

19. Hva er en basecase i rekursjon?

A.En tilstand som stopper rekursjonen.
B.En del av problemet som alltid må løses først.
C.Et mål for algoritmens effektivitet.
D.Den maksimale dybden av rekursjonen.

20. Hvilken tidskompleksitet har en algoritme med en rekursiv løsning som løser et problem i flere delproblemer?

A.O(n log n)
B.O(n^2)
C.O(2^n)
D.O(log n)

21. Hva er en ulempe med rekursjon?

A.Det kan føre til høy minnebruk.
B.Det vil alltid være tregere enn iterasjon.
C.Det kan ikke brukes i programmering.
D.Det er umulig å implementere.

22. Hva er en base case i konteksten av rekursjon?

A.Den mest kompliserte versjonen av et problem
B.Den enkleste versjonen av et problem som stopper rekursjonen
C.En del av en rekursiv funksjon
D.En iterativ løsning

23. Sammenlign rekursiv og iterativ løsning: hva er en viktig forskjell?

A.Rekursiv bruker funksjonskall, iterativ bruker løkker.
B.Rekursiv er alltid langsommere enn iterativ.
C.Iterativ bruker mer minne enn rekursiv.
D.Rekursjon kan ikke brukes til å løse matematiske problemer.

24. Hvilken av følgende er en fordel med memoization?

A.Reduserer tiden brukt ved å lagre tidligere beregnede resultater.
B.Øker minnebruken drastisk.
C.Fjerner behovet for rekursjon helt.
D.Gjør koden mer kompleks uten gevinst.

25. Hvilken av følgende beskriver tail rekursjon?

A.Den siste linjen i funksjonen er et rekursivt kall.
B.Rekursive kall gjøres før den endelige operasjonen.
C.Det er alltid en uendelig løkke.
D.Den bruker ikke minne.

26. Hvilken av følgende tilnærminger er rekursiv?

A.Bruk av løkker
B.Dynamisk programmering
C.Funksjoner som kaller seg selv
D.Greedy-algoritmer

27. Hvorfor velger vi ofte rekursjon i programmering?

A.For å gjøre koden mer lesbar og håndterlig.
B.For å øke hastigheten på programmet.
C.For å redusere mengden data.
D.For å unngå feil.

28. Sammenlign rekursjon og iterasjon. Hvilket utsagn er korrekt?

A.Rekursjon kan være enklere å lese, mens iterasjon kan være mer minneeffektiv.
B.Rekursjon er alltid raskere enn iterasjon.
C.Iterasjon er alltid enklere å implementere enn rekursjon.
D.Rekursjon bruker ikke minne.

29. Hvilket av følgende er IKKE en egenskap ved rekursive funksjoner?

A.De må alltid ha flere basis tilfeller.
B.De kan kalle seg selv.
C.De har en stoppbetingelse.
D.De kan dele opp problemet i mindre deler.

30. Hvilken påstand om minnebruk i rekursive funksjoner er sann?

A.Rekursjon bruker mindre minne enn iterasjon
B.Rekursjon kan føre til høy minnebruk
C.Rekursjon er alltid mer effektiv
D.Rekursjon reduserer stakkoverløp

31. Fill in the blank: Rekursjon er spesielt nyttig for _______.

A.problemer som kan deles opp i mindre, like problemer.
B.problemer med stor datamengde.
C.enkle, lineære problemer.
D.alle typer matematiske problemer.

32. Hva kan være en konsekvens av dyp rekursjon?

A.Stack overflow.
B.Økt ytelse.
C.Redusert minnebruk.
D.Ingen konsekvenser.

33. Hvordan kan man beskrive rekursiv dybde?

A.Antall nivåer med funksjonskall før basis tilfelle nås.
B.Antall variabler i en funksjon.
C.Tid brukt for å utføre en rekursiv funksjon.
D.Antall linjer med kode.

34. Hvilken av følgende er en korrekt definisjon av rekursiv funksjon?

A.En funksjon som kaller seg selv med samme argument
B.En funksjon som løser et problem ved å dele det opp i mindre delproblemer
C.En funksjon som aldri avslutter
D.En funksjon som alltid bruker sløyfer

35. Hvilke trinn er involvert i rekursjon?

A.Definer problemet, bestem basecase, kall funksjonen.
B.Skriv koden, test den, forbedre den.
C.Lag et diagram, skriv pseudokode, implementere.
D.Identifiser variabler, definere datatyper, optimalisere.

36. Hvilken av følgende beskriver dynamisk programmering?

A.En teknikk for å løse problemer ved å dele dem inn i mindre delproblemer og lagre resultater.
B.En måte å unngå rekursjon helt.
C.En metode for å øke rekkefølgen av funksjonskall.
D.En algoritme som alltid er mer effektiv enn rekursjon.

37. Hvilken av følgende definisjoner beskriver en rekursiv funksjon?

A.En funksjon som kaller seg selv.
B.En funksjon uten parametere.
C.En funksjon som alltid returnerer null.
D.En funksjon som bare bruker løkker.

38. Når er det mest hensiktsmessig å bruke indirekte rekursjon?

A.Når et problem kan løses av flere funksjoner
B.Når delproblemet er enkelt
C.Når det er behov for høy hastighet
D.Når minnebruk ikke er en faktor

39. Sann eller usann: Rekursjon kan føre til stack overflow.

A.Sann.
B.Usann.
C.Bare i tilfeller med store data.
D.Bare ved feil implementering.

40. Hvorfor kan naive rekursive løsninger være ineffektive?

A.De kan gjøre mange unødvendige beregninger.
B.De bruker alltid lite minne.
C.De er enkle å implementere.
D.De oppnår alltid optimal ytelse.

41. Hvordan sammenlignes rekursjon og iterasjon?

A.Rekursjon bruker funksjonskall, mens iterasjon bruker løkker.
B.Rekursjon er alltid raskere enn iterasjon.
C.Iterasjon er mer lesbar enn rekursjon.
D.Rekursjon bruker alltid mindre minne enn iterasjon.

42. Hvilket av følgende er ikke en fordel med rekursjon?

A.Forenkler koding av komplekse oppgaver
B.Reduserer koden betydelig
C.Kan føre til stakkoverløp
D.Er intuitiv for mange problemer

43. Hva er algoritmisk tenkning?

A.Evnen til å utvikle trinnvise løsningsmetoder.
B.En metode for å evaluere kodesikkerhet.
C.En tilnærming for å skrive programmer i lavnivå språk.
D.En teknikk for å forbedre programytelse.

44. Hvilket av følgende er IKKE en faktor som påvirker effektiviteten til rekursive funksjoner?

A.Antall rekursive kall.
B.Dybden av rekursjonen.
C.Antall variabler i algoritmen.
D.Hvor mye arbeid som gjøres i hvert kall.

45. Hva er definisjonen for faktorial i rekursjon?

A.n! = n * (n-1)! med 0! = 1.
B.n! = n + (n-1)! med 0! = 0.
C.n! = n - (n-1)! med 1! = 1.
D.n! = n / (n-1)! med 1! = 1.

46. Hvilket av følgende påstander er korrekt når man sammenligner direkte og indirekte rekursjon?

A.Direkte rekursjon kaller alltid seg selv direkte, mens indirekte rekursjon involverer flere funksjoner.
B.Indirekte rekursjon er alltid raskere enn direkte rekursjon.
C.Direkte rekursjon kan bare brukes for matematiske beregninger, mens indirekte rekursjon kan brukes for alt.
D.Ingen av alternativene er riktige.

47. Hva beskriver rekursjonens kompleksitet?

A.Tid og plasskompleksitet påvirket av rekursive kall.
B.Antall kodelinjer i en funksjon.
C.Kostnaden ved å kjøre en algoritme.
D.Sikkerheten i en programkode.

48. Hvilken type problem er spesielt godt egnet for rekursive løsninger?

A.Problemer som kan deles opp i mindre delproblemer.
B.Problemer med konstant tid og plasskompleksitet.
C.Alle typer algoritmiske problemer.
D.Problemer som krever iterativ beregning.

49. Hvilket av følgende er et eksempel på et problem som kan løses rekursivt?

A.Beregning av Fibonacci-tall.
B.Sortering av en liste.
C.Søking i en database.
D.Kalkulering av en sum ved hjelp av en for-løkke.

50. Hva er en rekursiv algoritme?

A.En algoritme som løser problemer ved å bruke seg selv.
B.En lineær algoritme for datainnsamling.
C.En metode for å komprimere data.
D.En algoritme for å sortere i stigende rekkefølge.

51. Hva skjer med ytelsen når et problem løses ved hjelp av både rekursjon og memoization?

A.Ytelsen forbedres betydelig.
B.Ytelsen reduseres.
C.Ingen signifikant endring.
D.Ytelsen blir alltid dårligere.

52. Hvorfor kan rekursjon være mindre minneeffektiv enn iterasjon?

A.Fordi hver rekursiv funksjonskall bruker ekstra minne på stabelen.
B.Fordi rekursjon alltid er tregere.
C.Fordi rekursjon krever flere variabler.
D.Fordi iterasjon bruker mer CPU-kraft.

53. Gi et eksempel på praktisk bruk av rekursjon.

A.Dybde-først søk i trær.
B.Bubblesort av en liste.
C.Den lineære søkemetoden.
D.Hashing av data.

54. Hvilket av følgende er en ulempe med rekursive funksjoner?

A.De kan bruke mye minne på grunn av kallstakken.
B.De er alltid raskere enn iterative løsninger.
C.De er enklere å forstå enn iterative løsninger.
D.De krever ingen ekstra ressurser.

55. Hva er den primære hensikten med å implementere rekursjon?

A.Å oppnå en løsning på komplekse problemer på en enklere måte.
B.Å komplisere programmet.
C.Å eliminere behovet for variabler.
D.Å redusere hvor mye kode som må skrives.

56. Hvilket av følgende beskriver best hva som skjer når en funksjon er rekursiv?

A.Den kaller seg selv med et nytt argument for å løse et problem.
B.Den oppretter en ny variabel for hvert anrop.
C.Den utfører en løkke for å repetere oppgaven.
D.Den avslutter programmet hvis betingelsen ikke er oppfylt.

Relaterte studiesett

Lag ditt eget studiesett

Last opp en PDF, lim inn notatene dine, eller beskriv et tema – AI genererer flashkort, quizer og mer på sekunder.