Datalogi C (NatBas):
Kort læsevejledning til kapitel 7

Rekursion er kun svært at forstå hvis man får det serveret som et problem. Vor lærebog synes jeg ikke slipper særligt godt fra præsentationen af rekursion.

For at gøre rekursion let tilgængeligt forklarer forfatteren grundprincippet ud fra at det blot er en anvendelse af matematisk induktion som i induktionsbeviser.

Ikke særligt smart efter min mening: Rekursion er den banale ting at en procedure blandt de ting, den kalder, også kalder sig selv, og det er der intet underligt i.

Induktionsbeviser, derimod, er en erkendelsesmæssig meget hård nød at knække og for de fleste er der ikke meget andet end at tro på at princippet virker, da man skal ned og rode i noget fælt grundlagsmatematik for virkeligt at forstå det.

Til l&oaelig;sning af bogens kapitel 7: Allerførst spring op og fald ned på beviserne, dem er der ingen der vil kræve af jer at I kan reproducere end sige forstå. Det vigtigste er eksemplerne, og det bedste eksempel er binær søgning formuleret rekursivt, som vi også så på i forelæsningen 17/9: Binær søgning er meget lettere at forstå, hvis man beskriver det rekursivt! Og der er sådan set hovedpointen.

Del-og-hersk-princippet, som er beskrevet i afsnit 7.5, er ganske udmærket at have med i sin mentale værktøjskasse, og formlen s. 265 til at vurdere tidskompleksitet på sådanne algoritmer er nyttig (godt at vide hvor man kan slå den op og at kunne finde ud af at bruge den). Eksemplet med "maximum contiguous subsequence problem" er godt til at illustrere del-og-hersk, så brug lidt energi på at forstå den (også selv om den løser et lidt sygt problem). Vi kommer senere til lidt mere interessante del-og-hersk algritmer, men vi kender allerede en: Binær søgning - et perfekt eksempel på del-og-hersk... hvor det særlige er, at man splitter problemet op i et delproblem som er halv så stort og (følgeligt) er omkostningen ved at kombinere delløsningerne = 0, da der kun er en delløsning :)

Afsnittet om "dynamisk programmering" er ganske udmærket omend dets motiverende eksempel (at give byttepenge) ikke er det bedste. Iøvrigt: Der er ikke noget god begrundelse for betegnelsen "dynamisk programmering" - den er ikke specielt mere dynamisk end så meget andet, så øh ja, historisk betinget.

Princippet i dynamisk programmering kan forklares relativt enkelt:
Vi skal løse et problem P(n) (f.eks. "give beløbet n kr. tilbage i så få sedler og mønter som muligt). Hvis vi nu i forvejen rent intellektuelt kan regne ud, at for at løse P(n) får vi brug for, direkte eller indirekte, at kende løsningen på P(1), P(2), ..., P(n-1), jamen så kan vi lige så godt beregne dem alle fra en ende af og bygge en tabel