I dette afsnit ser vi på det mere tekniske aspekt af rekursive funktioner i C. Dette er for øvrigt stort set det perspektiv som dyrkes i kapitel 11 af C by Dissection.

33.1 Basal rekursion (1) 33.2 Basal rekursion (2)

 

33.1.  Basal rekursion (1)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Programmerne i program 33.1 og program 33.2 er næsten funktionelt identiske. Begge gentager - på en forholdsvis besværlig måde - udskriften 'f: i', hvor i er et lille heltal.

I program 33.2 benytter vi en funktion, som kalder sig selv rekursivt. I program 33.1 har vi håndlavet et antal versioner af f, som kalder hinanden. I forhold til både program 33.1 og program 33.2 ville det være lettere at skrive en simpel for-løkke. Men programmerne illustrerer hvordan vi kan bruge rekursion til simple former for gentagelser i stedet for at bruge løkker.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#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;
}

Grundtilfældet i en rekursiv definition svarer til et delproblem, som ofte er så simpelt¨, at det kan løses umiddelbart uden yderlig problemopsplitning.

33.2.  Basal rekursion (2)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

I dette afsnit vil vi i større detalje undersøge hvad der sker når en funktion kalder sig selv rekursivt. Vi vil se på stakken af aktiveringer (activation records), og vi vil i den forbindelse se på kommandoer som udføres før og efter de rekursive kald.

I program 33.3 ser vi main, som kalder den rekursive funktion f. Kaldene af f, herunder det rekursive kald, svarer til de blå dele i programmet.

I funktionen f indlæses der et tegn med scanf inden det rekursive kald af f. Efter det rekursive kald af f udskrives det indlæste tegn.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#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;
}

Herunder, i program 33.4 viser vi en dialog med program 33.3 hvor tegnene 'a', 'b', 'c' og 'd' indlæses i den lokale variabel ch. Hert nyt tegn indlæses i et separat rekursivt kald af f. Bemærk at der på denne måde kan sameksistere et antal ch variable - én pr. kald af f.

1
2
3
4
5
6
7
8
9
10
11

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'

Hvis du skifter til den slide, som svarer til dette afsnit, kan du følge udvikling af kaldstakken, som modsvarer kørslen af program 33.3. Du kan også starte her.

Ved at følge udviklingen af kaldstakken skal du bide mærke i hvordan variablene i og ch optræder i alle kald af f. Man kan kun tilgå variable i den øverste ramme på stakken. Variable under toppen af stakken kan først tilgås når kaldene svarende til de øvre rammer er kørt til ende.

Læg også mærke til at tegnene a, b, c og d, som indlæses på vej op ad stakken udskrives i modsat rækkefølge på vej ned ad stakken.