Kurt Nørmark ©
Institut for Datalogi, Aalborg Universitet

Sammendrag Forrige lektion Næste lektion Stikord Referencer Indhold

Emnet for denne lektion er rekursion.

Begrebet rekursion: Rekursion er en problemløsningside, som involverer løsning af delproblemer af samme slags som det overordnede problem

Rekursive strukturer I en rekursiv struktur kan man genfinde helheden i detaljen I datalogisk sammenhæng arbejder vi ofte med rekursive datastrukturer Rekursive processer Rekursive strukturer processeres naturligt rekursivt Rekursive processer programmeres med rekursive procedurer eller funktioner

Henvisninger Vores første behandling af rekursion ECIU materiale om rekursion - bedst i IE med SVG, Flash og Java plugins

Hverdagsrekursion (1) Slide Indhold Stikord Referencer Lærebog

Man kan opnå et rekursivt billede hvis et spejl spejler sig et i et andet spejl Tilsvarende rekursive billeder fåes hvis man filmer et TV med kamera, som samtidigt viser signalet fra kameraet

Figur. Et billede af en del af en computerskærm, optaget med et web kamera, hvis billede samtidigt vises på skærmen. Det rekursive billede opstår fordi vinduet på skærmen filmes af kameraet, som viser det optagede billede som en del af vinduet, som hermed påvirker hvad kameraet filmer, som hermed påvirker billedet, osv. Efter nogle få niveuaer fortoner effekten sig i et meget forvrænget billede.

Hverdagsrekursion (2) Slide Indhold Stikord Referencer Lærebog

Det er muligt - men næppe naturligt - at opfatte en trappe som en rekursiv struktur

Figur. En trappe opfattet som en rekursiv struktur.

En rekursiv trappe: En trappe kan være 'tom' - flad gulv En trappe kan bestå af et trin og en tilstødende trappe

Henvisning Tilsvarende eksempel: Lister

En funktion i C er rekursiv hvis den i nogle programtilstande kalder sig selv direkte eller indirekte

Program: Funktionen main som kalder en funktion f3, som kalder f2, og som kalder f1.

#include <stdio.h> void f1(int i){ printf("f1: %i\n", i); } void f2(int i){ printf("f2: %i\n", i); f1(i-1); } void f3(int i){ printf("f3: %i\n", i); f2(i-1); } int main(void) { printf("main\n"); f3(3); return 0; }

Program: En tilsvarende kæde af rekusive kald.

#include <stdio.h> void f(int i){ if (i >= 1){ printf("f: %i\n", i); f(i-1); } } int main(void) { printf("main\n"); f(3); return 0; }

For at sikre at programmet afsluttes, skal der eksistere et grundtilfælde (en programtilstand) hvor funktionen undlader at kalde sig selv rekursivt

Basal rekursion (2) Slide Indhold Stikord Referencer Lærebog

Vi viser her en variation af programmet, som afslører flere interessante aspekter af rekursion

Program: Læsning på vej op ad bakken/stakken - Skrivning på vej ned.

#include <stdio.h> void f(int i){ char ch, skipch; if (i >= 1){ printf("Enter a character: "); scanf("%c%c", &ch, &skipch); f(i-1); printf("We read: '%c'\n", ch);} else printf("No more recursive calls\n"); } int main(void) { f(4); return 0; }

Program: Input til og output fra programmet.

Enter a character: a Enter a character: b Enter a character: c Enter a character: d Enter a character: e No more recursive calls We read: 'e' We read: 'd' We read: 'c' We read: 'b' We read: 'a'

Billedserie: En illustration af den rekursive udvikling af kaldet f(4)

En illustration af den rekursive udvikling af kaldet f(4)

Billed nr. 1. Kaldet f(4). Brugeren promptes for et tegn, og der gives et 'a'.

 

Billed nr. 2. Kaldet f(3). Brugeren promptes igen for et tegn, og der gives denne gang et 'b'.

 

Billed nr. 3. Kaldet f(2). Brugeren promptes igen for et tegn, og der gives denne gang et 'c'.

 

Billed nr. 4. Kaldet f(1). Brugeren promptes sidste gang for et tegn, og der gives denne gang et 'd'.

 

Billed nr. 5. Kaldet f(0). Else delen vil udskrive 'No more recursive calls'.

 

Billed nr. 6. På vej ned ad stakken udføres det afsluttende printf i if delen. Her udskrives 'd'.

 

Billed nr. 7. Her udskrives 'c'

 

Billed nr. 8. Og her udskrives 'b'

 

Billed nr. 9. Slutteligt udskrives 'a'. Bemærk disciplinen 'first in, last out' som er typisk for en stak.

 

Vi har i tidligere lektioner mødt flere eksempler på rekursive funktioner

Program: Et program med en rekursivt defineret fakultetsfunktion.

#include <stdio.h> unsigned long factorial(unsigned long n){ if (n == 0) return 1; else return n * factorial(n - 1); } int main(void) { unsigned long k; for (k = 1; k <= 12; k++) printf("%-20lu %20lu\n", k, factorial(k)); return 0; }

Program: Output fra ovenstående program.

1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 11 39916800 12 479001600

Program: En rekursiv version af funktionen findRootBetween.

double findRootBetween(double l, double u){ if (isSmallNumber(f(middleOf(l,u)))) return middleOf(l,u); else if (sameSign(f(middleOf(l,u)), f(u))) return findRootBetween(l, middleOf(l,u)); else if (!sameSign(f(middleOf(l,u)), f(u))) return findRootBetween(middleOf(l,u),u); else exit (-1); }

Program: Hele rodsøgningsprogrammet.

#include <stdio.h> #include <math.h> double f (double x){ /* (x - 5.0) * (x - 3.0) * (x + 7.0) */ return (x*x*x - x*x - 41.0 * x + 105.0); } int sameSign(double x, double y){ return x * y >= 0.0; } double middleOf(double x, double y){ return x + (y - x)/2; } int isSmallNumber(double x){ return (fabs(x) < 0.0000001); } double findRootBetween(double l, double u){ if (isSmallNumber(f(middleOf(l,u)))) return middleOf(l,u); else if (sameSign(f(middleOf(l,u)), f(u))) return findRootBetween(l, middleOf(l,u)); else if (!sameSign(f(middleOf(l,u)), f(u))) return findRootBetween(middleOf(l,u),u); else exit (-1); } int main (void){ double x, y; int numbers; printf("RECURSIVE ROOT FINDING\n\n"); do{ printf("%s","Find a ROOT between which numbers: "); numbers = scanf("%lf%lf", &x, &y); if (numbers == 2 && !sameSign(f(x),f(y))){ double solution = findRootBetween(x,y); printf("\nThere is a root in %lf\n", solution); } else if (numbers == 2 && sameSign(f(x),f(y))) printf("\nf must have different signs in %lf and %lf\n", x, y); else if (numbers != 2) printf("\nBye\n\n"); } while (numbers == 2); }

Program: Rekursiv udgave af strcmp - fra opgaveregningen i forrige lektion.

int mystrcmp(const char* s1, const char* s2){ int result; if (*s1 == '\0' && *s2 == '\0') result = 0; else if (*s1 == '\0' && *s2 != '\0') result = -1; else if (*s1 != '\0' && *s2 == '\0') result = 1; else if (*s1 < *s2) result = -1; else if (*s1 > *s2) result = 1; else /* (*s1 == *s2) */ result = mystrcmp(s1+1, s2+1); return result; }

Vi vil nu se på flere eksempler

Fibonacci tal (1) Slide Indhold Stikord Referencer Lærebog

Serien af Fibonacci tal er en klassisk talrække, i hvilken hvert tal er summen af de to foregående tal

Program: Funktionen fib der udregner det n'te Fibonaccital.

long fib(long n){ long result; if (n == 0) result = 0; else if (n == 1) result = 1; else result = fib(n-1) + fib(n-2); return result; }

Program: Hele programmet.

#include <stdio.h> long fib(long n){ long result; if (n == 0) result = 0; else if (n == 1) result = 1; else result = fib(n-1) + fib(n-2); return result; } int main(void) { long i; for(i = 0; i < 100; i++) printf("Fib(%li) = %li\n", i, fib(i)); return 0; }

Program: En udgave af programmet som holder regnskab med antallet af additioner.

#include <stdio.h> long plus_count = 0; long fib(long n){ long result; if (n == 0) result = 0; else if (n == 1) result = 1; else { result = fib(n-1) + fib(n-2); plus_count++; } return result; } int main(void) { long i, fib_res; for(i = 0; i < 42; i++){ plus_count = 0; fib_res = fib(i); printf("Fib(%li) = %li (%li)\n", i, fib_res, plus_count ); } return 0; }

Fibonacci tal (2) Slide Indhold Stikord Referencer Lærebog

Funktionen fib foretager store mængder af unødvendige genberegninger Antallet af additioner vokser eksponentielt i forhold til parameteren n

Figur. En illustration af beregningsprocessen af fib(5)

Mere effektive løsninger En simpel iterativ løsning En rekursiv løsning, som kortslutter genberegningerne

Fibonacci tal (3) Slide Indhold Stikord Referencer Lærebog

Vi viser her mere effektive udgaver af fib funktionen

Program: En iterativ udgave af fib programmeret med en forløkke.

#include <stdio.h> long fib(long n){ long small, large, temp, m; for (small = 0, large = 1, m = 0; m < n; m++){ temp = small; small = large; large = large + temp; } return small; } int main(void) { long i; for(i = 0; i < 100; i++){ printf("Fib(%li) = %li\n", i, fib(i) ); } return 0; }

Program: En memoriseret udgave af fib.

#include <stdio.h> long fib(long n){ long result; static long memo[100]; /* elements pre-initialized to 0 */ if (n == 0) result = 0; else if (n == 1) result = 1; else if (memo[n] != 0) result = memo[n]; else { result = fib(n-1) + fib(n-2); memo[n] = result; } return result; } int main(void) { long i; for(i = 0; i < 100; i++) printf("Fib(%li) = %li\n", i, fib(i)); return 0; }

Potensopløftning (1) Slide Indhold Stikord Referencer Lærebog

På denne side viser vi en simpel, rekursiv potensopløftningsfunktion

Program: Den simple power funktion.

double power(double number, int pow){ double result; if (pow == 0) result = 1.0; else if (pow > 0) result = number * power(number, pow - 1); else result = 1.0 / power(number, -pow); return result; }

Beregningsidé: potens > 0:         tal potens = tal potens-1 · tal potens = 0:         tal 0 = 1.0 potens < 0:         1.0 / tal -potens

Potensopløftning (2) Slide Indhold Stikord Referencer Lærebog

På denne side viser vi en mere effektiv rekursiv potensopløftningsfunktion

Program: Den hurtige power funktion.

double power(double number, int pow){ double result; printf("power(%lf,%i)\n", number, pow); if (pow == 0) result = 1.0; else if (pow > 0 && even(pow)) result = sqr(power(number,pow/2)); else if (pow > 0 && odd(pow)) result = number * power(number, pow - 1); else result = 1.0 / power(number, -pow); return result; }

Beregningsidé: potens > 0, potens er lige:         tal potens = ( tal potens/2 ) 2 potens > 0, potens er ulige         tal potens = tal potens-1 · tal potens = 0:         tal 0 = 1.0 potens < 0:         1.0 / tal -potens

Potensopløftning (3) Slide Indhold Stikord Referencer Lærebog

Der er meget stor forskel på antallet af multiplikationer i de to udgaver af potensopløftningsfunktionen Vi illustrerer herunder rekursionens udvikling af den hurtige power funktion Vi skriver også et program som belyser forskellen mellem antallet af udførte multiplikationer

Billedserie: Illustration af kaldet power(2.0,10), hvor power er den effektive version.

Illustration af kaldet power(2.0,10), hvor power er den effektive version.

Billed nr. 1. Kaldet power(2.0,10). Result har ikke fået en værdi.

 

Billed nr. 2. Da 10 er lige forårsages det rekursive kald power(2.0,5)

 

Billed nr. 3. Da 5 er ulige kaldes power(2.0,4).

 

Billed nr. 4. For 4 lige kaldes power(2.0,2)

 

Billed nr. 5. Da 2 er lige kaldes power(2.0,1). Bemærk stadig, at ingen af result variablene har fået en værdi

 

Billed nr. 6. Vi når til til kaldet power(2.0.0) som er basistilfældet i rekursionen.

 

Billed nr. 7. En gentagelse af det tidligere billede, hvor result har fået værdien 1.0

 

Billed nr. 8. Result bliver her 2.0 * 1.0, altså 2.0

 

Billed nr. 9. Result er sqr(2.0), altså 4.0

 

Billed nr. 10. Result er sqr(4.0), altså 16.0

 

Billed nr. 11. Da pow er ulige på dette niveau bliver result 2.0 * 16.0, altså 32.0

 

Billed nr. 12. Da pow er 10 på dette niveau kvadreres det forrige resultat, altså sqr(32.0), som er 1024.0

 

Program: Et program der tæller antallet af multiplikationer i de to potens funktioner.

#include <stdio.h> double sqr(double); int even (int); int odd (int); int mult_no_1, mult_no_2; double power1(double number, int pow){ double result; if (pow == 0) result = 1.0; else if (pow > 0){ result = number * power1(number, pow - 1); mult_no_1++; } else result = 1.0 / power1(number, -pow); return result; } double power2(double number, int pow){ double result; if (pow == 0) result = 1.0; else if (pow > 0 && even(pow)){ result = sqr(power2(number,pow/2)); mult_no_2++; } else if (pow > 0 && odd(pow)){ result = number * power2(number, pow - 1); mult_no_2++; } else result = 1.0 / power2(number, -pow); return result; } int main(void) { int i; double res1, res2; for(i = 1; i < 500; i += 5){ mult_no_1 = 0; mult_no_2 = 0; res1 = power1(1.01,i); res2 = power2(1.01,i); printf("power1(1.01,%i) = %7.5f (%i multiplications)\n" "power2(1.01,%i) = %7.5f (%i multiplications). \n\n", i, res1, mult_no_1, i, res2, mult_no_2); } return 0; } double sqr(double d){ return d*d;} int even (int i){ return i % 2 == 0;} int odd (int i){ return i % 2 != 0;}

Program: Output fra programmet.

power1(1.01,1) = 1.01000 (1 multiplications) power2(1.01,1) = 1.01000 (1 multiplications). power1(1.01,6) = 1.06152 (6 multiplications) power2(1.01,6) = 1.06152 (4 multiplications). power1(1.01,11) = 1.11567 (11 multiplications) power2(1.01,11) = 1.11567 (6 multiplications). power1(1.01,16) = 1.17258 (16 multiplications) power2(1.01,16) = 1.17258 (5 multiplications). power1(1.01,21) = 1.23239 (21 multiplications) power2(1.01,21) = 1.23239 (7 multiplications). power1(1.01,26) = 1.29526 (26 multiplications) power2(1.01,26) = 1.29526 (7 multiplications). power1(1.01,31) = 1.36133 (31 multiplications) power2(1.01,31) = 1.36133 (9 multiplications). power1(1.01,36) = 1.43077 (36 multiplications) power2(1.01,36) = 1.43077 (7 multiplications). power1(1.01,41) = 1.50375 (41 multiplications) power2(1.01,41) = 1.50375 (8 multiplications). power1(1.01,46) = 1.58046 (46 multiplications) power2(1.01,46) = 1.58046 (9 multiplications). power1(1.01,51) = 1.66108 (51 multiplications) power2(1.01,51) = 1.66108 (9 multiplications). power1(1.01,56) = 1.74581 (56 multiplications) power2(1.01,56) = 1.74581 (8 multiplications). power1(1.01,61) = 1.83486 (61 multiplications) power2(1.01,61) = 1.83486 (10 multiplications). power1(1.01,66) = 1.92846 (66 multiplications) power2(1.01,66) = 1.92846 (8 multiplications). power1(1.01,71) = 2.02683 (71 multiplications) power2(1.01,71) = 2.02683 (10 multiplications). power1(1.01,76) = 2.13022 (76 multiplications) power2(1.01,76) = 2.13022 (9 multiplications). power1(1.01,81) = 2.23888 (81 multiplications) power2(1.01,81) = 2.23888 (9 multiplications). power1(1.01,86) = 2.35309 (86 multiplications) power2(1.01,86) = 2.35309 (10 multiplications). power1(1.01,91) = 2.47312 (91 multiplications) power2(1.01,91) = 2.47312 (11 multiplications). power1(1.01,96) = 2.59927 (96 multiplications) power2(1.01,96) = 2.59927 (8 multiplications). power1(1.01,101) = 2.73186 (101 multiplications) power2(1.01,101) = 2.73186 (10 multiplications). power1(1.01,106) = 2.87121 (106 multiplications) power2(1.01,106) = 2.87121 (10 multiplications). power1(1.01,111) = 3.01768 (111 multiplications) power2(1.01,111) = 3.01768 (12 multiplications). power1(1.01,116) = 3.17161 (116 multiplications) power2(1.01,116) = 3.17161 (10 multiplications). power1(1.01,121) = 3.33339 (121 multiplications) power2(1.01,121) = 3.33339 (11 multiplications). power1(1.01,126) = 3.50343 (126 multiplications) power2(1.01,126) = 3.50343 (12 multiplications). power1(1.01,131) = 3.68214 (131 multiplications) power2(1.01,131) = 3.68214 (10 multiplications). power1(1.01,136) = 3.86996 (136 multiplications) power2(1.01,136) = 3.86996 (9 multiplications). power1(1.01,141) = 4.06737 (141 multiplications) power2(1.01,141) = 4.06737 (11 multiplications). power1(1.01,146) = 4.27485 (146 multiplications) power2(1.01,146) = 4.27485 (10 multiplications). power1(1.01,151) = 4.49291 (151 multiplications) power2(1.01,151) = 4.49291 (12 multiplications). power1(1.01,156) = 4.72209 (156 multiplications) power2(1.01,156) = 4.72209 (11 multiplications). power1(1.01,161) = 4.96296 (161 multiplications) power2(1.01,161) = 4.96296 (10 multiplications). power1(1.01,166) = 5.21613 (166 multiplications) power2(1.01,166) = 5.21613 (11 multiplications). power1(1.01,171) = 5.48220 (171 multiplications) power2(1.01,171) = 5.48220 (12 multiplications). power1(1.01,176) = 5.76185 (176 multiplications) power2(1.01,176) = 5.76185 (10 multiplications). power1(1.01,181) = 6.05576 (181 multiplications) power2(1.01,181) = 6.05576 (12 multiplications). power1(1.01,186) = 6.36466 (186 multiplications) power2(1.01,186) = 6.36466 (12 multiplications). power1(1.01,191) = 6.68933 (191 multiplications) power2(1.01,191) = 6.68933 (14 multiplications). power1(1.01,196) = 7.03055 (196 multiplications) power2(1.01,196) = 7.03055 (10 multiplications). power1(1.01,201) = 7.38918 (201 multiplications) power2(1.01,201) = 7.38918 (11 multiplications). power1(1.01,206) = 7.76610 (206 multiplications) power2(1.01,206) = 7.76610 (12 multiplications). power1(1.01,211) = 8.16225 (211 multiplications) power2(1.01,211) = 8.16225 (12 multiplications). power1(1.01,216) = 8.57861 (216 multiplications) power2(1.01,216) = 8.57861 (11 multiplications). power1(1.01,221) = 9.01620 (221 multiplications) power2(1.01,221) = 9.01620 (13 multiplications). power1(1.01,226) = 9.47612 (226 multiplications) power2(1.01,226) = 9.47612 (11 multiplications). power1(1.01,231) = 9.95950 (231 multiplications) power2(1.01,231) = 9.95950 (13 multiplications). power1(1.01,236) = 10.46753 (236 multiplications) power2(1.01,236) = 10.46753 (12 multiplications). power1(1.01,241) = 11.00148 (241 multiplications) power2(1.01,241) = 11.00148 (12 multiplications). power1(1.01,246) = 11.56267 (246 multiplications) power2(1.01,246) = 11.56267 (13 multiplications). power1(1.01,251) = 12.15248 (251 multiplications) power2(1.01,251) = 12.15248 (14 multiplications). power1(1.01,256) = 12.77238 (256 multiplications) power2(1.01,256) = 12.77238 (9 multiplications). power1(1.01,261) = 13.42390 (261 multiplications) power2(1.01,261) = 13.42390 (11 multiplications). power1(1.01,266) = 14.10865 (266 multiplications) power2(1.01,266) = 14.10865 (11 multiplications). power1(1.01,271) = 14.82833 (271 multiplications) power2(1.01,271) = 14.82833 (13 multiplications). power1(1.01,276) = 15.58473 (276 multiplications) power2(1.01,276) = 15.58473 (11 multiplications). power1(1.01,281) = 16.37970 (281 multiplications) power2(1.01,281) = 16.37970 (12 multiplications). power1(1.01,286) = 17.21523 (286 multiplications) power2(1.01,286) = 17.21523 (13 multiplications). power1(1.01,291) = 18.09338 (291 multiplications) power2(1.01,291) = 18.09338 (12 multiplications). power1(1.01,296) = 19.01633 (296 multiplications) power2(1.01,296) = 19.01633 (11 multiplications). power1(1.01,301) = 19.98635 (301 multiplications) power2(1.01,301) = 19.98635 (13 multiplications). power1(1.01,306) = 21.00586 (306 multiplications) power2(1.01,306) = 21.00586 (12 multiplications). power1(1.01,311) = 22.07737 (311 multiplications) power2(1.01,311) = 22.07737 (14 multiplications). power1(1.01,316) = 23.20353 (316 multiplications) power2(1.01,316) = 23.20353 (13 multiplications). power1(1.01,321) = 24.38715 (321 multiplications) power2(1.01,321) = 24.38715 (11 multiplications). power1(1.01,326) = 25.63114 (326 multiplications) power2(1.01,326) = 25.63114 (12 multiplications). power1(1.01,331) = 26.93858 (331 multiplications) power2(1.01,331) = 26.93858 (13 multiplications). power1(1.01,336) = 28.31272 (336 multiplications) power2(1.01,336) = 28.31272 (11 multiplications). power1(1.01,341) = 29.75695 (341 multiplications) power2(1.01,341) = 29.75695 (13 multiplications). power1(1.01,346) = 31.27486 (346 multiplications) power2(1.01,346) = 31.27486 (13 multiplications). power1(1.01,351) = 32.87019 (351 multiplications) power2(1.01,351) = 32.87019 (15 multiplications). power1(1.01,356) = 34.54690 (356 multiplications) power2(1.01,356) = 34.54690 (12 multiplications). power1(1.01,361) = 36.30914 (361 multiplications) power2(1.01,361) = 36.30914 (13 multiplications). power1(1.01,366) = 38.16127 (366 multiplications) power2(1.01,366) = 38.16127 (14 multiplications). power1(1.01,371) = 40.10788 (371 multiplications) power2(1.01,371) = 40.10788 (14 multiplications). power1(1.01,376) = 42.15378 (376 multiplications) power2(1.01,376) = 42.15378 (13 multiplications). power1(1.01,381) = 44.30405 (381 multiplications) power2(1.01,381) = 44.30405 (15 multiplications). power1(1.01,386) = 46.56400 (386 multiplications) power2(1.01,386) = 46.56400 (11 multiplications). power1(1.01,391) = 48.93923 (391 multiplications) power2(1.01,391) = 48.93923 (13 multiplications). power1(1.01,396) = 51.43562 (396 multiplications) power2(1.01,396) = 51.43562 (12 multiplications). power1(1.01,401) = 54.05936 (401 multiplications) power2(1.01,401) = 54.05936 (12 multiplications). power1(1.01,406) = 56.81693 (406 multiplications) power2(1.01,406) = 56.81693 (13 multiplications). power1(1.01,411) = 59.71516 (411 multiplications) power2(1.01,411) = 59.71516 (14 multiplications). power1(1.01,416) = 62.76124 (416 multiplications) power2(1.01,416) = 62.76124 (11 multiplications). power1(1.01,421) = 65.96269 (421 multiplications) power2(1.01,421) = 65.96269 (13 multiplications). power1(1.01,426) = 69.32745 (426 multiplications) power2(1.01,426) = 69.32745 (13 multiplications). power1(1.01,431) = 72.86385 (431 multiplications) power2(1.01,431) = 72.86385 (15 multiplications). power1(1.01,436) = 76.58064 (436 multiplications) power2(1.01,436) = 76.58064 (13 multiplications). power1(1.01,441) = 80.48702 (441 multiplications) power2(1.01,441) = 80.48702 (14 multiplications). power1(1.01,446) = 84.59266 (446 multiplications) power2(1.01,446) = 84.59266 (15 multiplications). power1(1.01,451) = 88.90774 (451 multiplications) power2(1.01,451) = 88.90774 (13 multiplications). power1(1.01,456) = 93.44293 (456 multiplications) power2(1.01,456) = 93.44293 (12 multiplications). power1(1.01,461) = 98.20946 (461 multiplications) power2(1.01,461) = 98.20946 (14 multiplications). power1(1.01,466) = 103.21913 (466 multiplications) power2(1.01,466) = 103.21913 (13 multiplications). power1(1.01,471) = 108.48434 (471 multiplications) power2(1.01,471) = 108.48434 (15 multiplications). power1(1.01,476) = 114.01813 (476 multiplications) power2(1.01,476) = 114.01813 (14 multiplications). power1(1.01,481) = 119.83420 (481 multiplications) power2(1.01,481) = 119.83420 (13 multiplications). power1(1.01,486) = 125.94695 (486 multiplications) power2(1.01,486) = 125.94695 (14 multiplications). power1(1.01,491) = 132.37151 (491 multiplications) power2(1.01,491) = 132.37151 (15 multiplications). power1(1.01,496) = 139.12379 (496 multiplications) power2(1.01,496) = 139.12379 (13 multiplications).

Hvert funktionskald kræver afsættelse af en activation record - lager til værdier af aktuelle parametre, lokale variable, og noget "internt bogholderi". En kæde af rekursive funktionskald kræver én activation record pr. kald/inkarnation af funktionen. Man skal være varsom med brug af rekursion som kan afstedkomme mange (tusinder) af rekursive kald. Dette kan føre til 'run time stack overflow'. Der findes en speciel form for rekursion hvor lagerforbruget kan optimaliseres Denne form kaldes halerekursion Halerekursion er tæt forbundet med iterative løsninger (brug af while eller for kontrolstrukturer).

Enhver løkke (ala while, do, for) kan let omprogrammeres med en (hale)rekursiv funktion. Nogle former for rekursion kan kun meget vanskeligt omprogrammeres med løkker.

Towers of Hanoi er en gammel asiatisk overlevering om munke, der skulle flytte 64 skiver fra én søjle til en anden Ifølge legenden ville templet og verden omkring det falde inden arbejdet kunne fuldføres

Figur. En illustration af Towers of Hanoi med fire skiver.

Towers of Hanoi (2) Slide Indhold Stikord Referencer Lærebog

Problemet: Flyt stakken af skiver fra venstre stang til højre stang med brug af midterste stang som 'mellemstation' Skiverne skal flyttes én ad gangen En større skive må aldrig placeres oven på en mindre skive

Henvisning Del og hersk

Løsningen på næste side er en rekursiv del og hersk løsning

Towers of Hanoi (3) Slide Indhold Stikord Referencer Lærebog

Vi programmerer en løsning på problemet som kun viser hvilke flytninger der skal foretages. Bogen har en løsning, som også viser hvordan tårnene ser ud efter hver flytning.

Program: Den centrale funktion i "Towers of Hanoi".

/* Move n discs from tower a to tower b via tower c */ void hanoi(int n, tower a, tower b, tower c){ if (n == 1) move_one_disc(a,b); else { hanoi(n-1,a,c,b); move_one_disc(a,b); hanoi(n-1,c,b,a); } }

Program: Hele programmet.

#include <stdio.h> enum tower {left, middle, right}; typedef enum tower tower; void move_one_disc(tower a, tower b); char *tower_out(tower t); /* Move n discs from tower a to tower b via tower c */ void hanoi(int n, tower a, tower b, tower c){ if (n == 1) move_one_disc(a,b); else { hanoi(n-1,a,c,b); move_one_disc(a,b); hanoi(n-1,c,b,a); } } void move_one_disc(tower a, tower b){ static long count = 0; count++; printf("%5i. Move disc from %6s tower to %6s tower\n", count, tower_out(a), tower_out(b)); } char *tower_out(tower t){ static char *result; switch (t){ case left: result = "LEFT"; break; case middle: result = "MIDDLE"; break; case right: result = "RIGHT"; break; } return result; } int main(void) { int number_of_discs; printf("How many discs: "); scanf("%d", &number_of_discs); hanoi(number_of_discs, left, right, middle); return 0; }

Program: Output fra programmet ved flytning af fire skiver.

1. Move disc from LEFT tower to MIDDLE tower 2. Move disc from LEFT tower to RIGHT tower 3. Move disc from MIDDLE tower to RIGHT tower 4. Move disc from LEFT tower to MIDDLE tower 5. Move disc from RIGHT tower to LEFT tower 6. Move disc from RIGHT tower to MIDDLE tower 7. Move disc from LEFT tower to MIDDLE tower 8. Move disc from LEFT tower to RIGHT tower 9. Move disc from MIDDLE tower to RIGHT tower 10. Move disc from MIDDLE tower to LEFT tower 11. Move disc from RIGHT tower to LEFT tower 12. Move disc from MIDDLE tower to RIGHT tower 13. Move disc from LEFT tower to MIDDLE tower 14. Move disc from LEFT tower to RIGHT tower 15. Move disc from MIDDLE tower to RIGHT tower

Towers of Hanoi (4) Slide Indhold Stikord Referencer Lærebog

Det er let at se at antallet af flytninger F(n) vokser eksponentielt med antallet af diske i tårnet. Mere præcist ser vi at F(n) = 2 n - 1.

Tabel. En table der viser antallet af flytninger og køretider af hanoi funktionen. Køretiderne i tredje kolonne er angivet under antagelsen af vi kan flytte 109 skiver pr. sekund. Køretiderne i fjerde kolonne er angivet under antagelsen af vi kan flytte 103 skiver pr. sekund.

n 2n 10-9 · 2n 10-3 · 2n 5 32 3.2 · 10-8 sek 3.2 · 10-2 sek 25 3.4 · 107 0.03 sek 9.3 timer 50 1.1 · 1015 13 dage 35702 år 65 3.7 · 1019 1170 år 1.17 · 109 år 80 1.2 · 1024 3.8 · 107 år 3.8 · 1013 år 100 1.2 · 1039 4.0 · 1013 år 4.0 · 1020 år

Quicksort er et eksempel på en rekursiv sorteringsteknik der typisk er meget mere effektiv end f.eks. boblesortering

Algoritmisk idé: Udvælg et vilkårligt deleelement blandt tabellens elementer Reorganiser tabellen således at den består af to dele: En venstre del hvor alle elementer er mindre end eller lig med deleelementet En højre del hvor alle elementer er større end eller lig med deleelementet Sorter både venstre og højre del af tabellen rekursivt, efter samme idé som netop beskrevet

Henvisning Boblesortering

Quicksort er et andet eksempel på en rekursiv del og hersk løsning En stor del af arbejdet består i opdelning af problemet i to mindre delproblemer, som egner sig til en rekursiv løsning Sammensætningen af delproblemernes løsninger er triviel

Quicksort (2) Slide Indhold Stikord Referencer Lærebog

Vi viser først den overordnede quicksort funktion Den viste udgave sorterer blot heltal

Program: Den rekursive quicksort funktion.

/* Sort the array interval a[from..to] */ void quicksort(element a[], index from, index to){ index point1, point2; if (from < to){ do_partitioning(a, from, to, &point1, &point2); partitioning_info(a, from, to, point1, point2); quicksort(a, from, point1); quicksort(a, point2, to); } }

Quicksort (3) Slide Indhold Stikord Referencer Lærebog

Den centrale del af quicksort er funktion do_partitioning

Program: Funktionen do_partitioning der opdeler tabellens elementer op i store og små.

/* Do a partitioning of a, and return the partitioning points in *point_left and *point_right */ void do_partitioning(element a[], index from, index to, index *point_left, index *point_right){ index i,j; element partitioning_el; i = from - 1; j = to + 1; partitioning_el = a[from]; do{ do {i++;} while (a[i] < partitioning_el); do {j--;} while (a[j] > partitioning_el); if (i < j) swap(&a[i],&a[j]); } while (i < j); if (i > j) { *point_left = j; *point_right = i;} else { *point_left = j-1; *point_right = i+1;} }

Program: Hele programmet.

#include <stdio.h> typedef int index; typedef int element; void do_partitioning(element[], index, index, index*, index*); void swap(index*, index*); void prn_array(char* s, int a[], int from, int to); void partitioning_info(element a[], index from, index to, index point_left, index point_right); /* Sort the array interval a[from..to] */ void quicksort(element a[], index from, index to){ index point1, point2; if (from < to){ do_partitioning(a, from, to, &point1, &point2); partitioning_info(a, from, to, point1, point2); quicksort(a, from, point1); quicksort(a, point2, to); } } void partitioning_info(element a[], index from, index to, index point_left, index point_right){ printf("Partitioning a[%i .. %i]\n", from, to); prn_array("Small:", a, from, point_left); printf("\n"); prn_array("Large:", a, point_left+1, to); printf("\n\n"); } /* Do a partitioning of a, and return the partitioning points in *point_left and *point_right */ void do_partitioning(element a[], index from, index to, index *point_left, index *point_right){ index i,j; element partitioning_el; i = from - 1; j = to + 1; partitioning_el = a[from]; do{ do {i++;} while (a[i] < partitioning_el); do {j--;} while (a[j] > partitioning_el); if (i < j) swap(&a[i],&a[j]); } while (i < j); if (i > j) { *point_left = j; *point_right = i;} else { *point_left = j-1; *point_right = i+1;} } int main(void) { int a[] = {7, 3, 66, 3, -5, 22, -77, 2}; int n; n = sizeof(a) / sizeof(int); prn_array("Before", a, 0, n-1); printf("\n\n"); quicksort(a, 0, n-1); prn_array(" After", a, 0, n-1); printf("\n\n"); putchar('\n'); return 0; } void swap(element *p, element *q) { element tmp; tmp = *p; *p = *q; *q = tmp; } void prn_array(char* s , int a[], int from, int to) { int i; printf("%s a[%i,%i]: ", s, from, to); for (i = from; i <= to; ++i) printf("%5d", a[i]); }

Billedserie: Scenarier der viser opdelingen i små og store elementer

Scenarier der viser opdelingen i små og store elementer

Billed nr. 1. Startsituationen forud for partitioneringen af tabellen. Deleelementet udvælges som det første. Variablen i tælles op sålænge elementerne er mindre end deleelementet. j tælles tilsvarende ned sålænge elementerne er større end deleelementet.

 

Billed nr. 2. Element i er større end deleelementet. Element j er mindre. De to ombyttes.

 

Billed nr. 3. Området med små og store elementer kan gøres lidt større efter ombytningen. i og j bevæges igen mod midten.

 

Billed nr. 4. i og j mødes...

 

Billed nr. 5. ... eller i og j overhaler hinanden.

 

Quicksort (4) Slide Indhold Stikord Referencer Lærebog

En god implementation plejer at være blandt de allerbedste sorteringsmetoder - men der er ingen garanti

Køretid i bedste tilfælde: I størrelsesordenen n · log2 (n) sammenligninger og ombytninger. Køretid i værste tilfælde I størrelsesordenen n2 sammenligninger og ombytninger.

Tabel. En tabel der illustrerer forskellen på væksten af n2 og n · log2 (n)

n n2 n · log2 (n) 100 10.000 664 1000 1.000.000 9.966 10.000 100.000.000 132.887 100.000 10.000.000.000 1.660.964

Det kan vises at en sortering med i størrelsesordenen n · log (n) sammenligninger og ombytninger er optimal.

Kapitel 8: Rekursion
Kursets hjemmeside     Forfatteren's hjemmeside     Om frembringelsen af disse sider     Forrige lektion (top)     Næste lektion (top)     Forrige lektion (bund)     Næste lektion (bund)     
Genereret: 7. Juli 2010, 15:12:21