En rekursiv funktion er kendetegnet ved, at den kalder sig selv. Men som det mest væsentlige, er rekursive funktioner udtryk for en problemløsning, hvor delproblemerne ligner det overordnede problem.

Vi introducerer rekursion i dette kapitel. I en senere lektion, startende i kapitel 32, vender vi tilbage til rekursion med fornyet styrke.

14.1 Rekursive funktioner

 

14.1.  Rekursive funktioner
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Først gør vi os de essentielle iagttagelser om rekursion, problemer som har rekursivt forekommende delproblemer:

Som det første eksempel programmerer vi fakultetsfunktionen. Hvis vi af bekvemmelighed her kalder fakultetsfunktionen for f, gælder at f(n) = n ^. (n-1) ^. (n-2) ^. ... 2 ^. 1. Dette kan også udtrykkes rekursivt som følger:

• f(n) = n ^. f(n-1)    for n > 0
• f(0) = 1

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

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

Som de fleste nok ved i forvejen vokser fakultetsfunktionen ganske voldsomt. Så voldsomt at vi højst kan beregne factorial(12), selv med tal i typen long. Vi viser outputtet af program 14.1 i program 14.2.

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

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

Som endnu et eksempel viser vi en rekursiv udgave af rodsøgningsfunktionen findRootBetween i program 14.3. Vi mødte den iterative (gentagende) udgave i program 13.1. Gentagelsen blev i dette program lavet med en while løkke.

1
2
3
4
5
6
7
8
9

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

Vi lægger mærke til, at der ikke anvendes nogen form for løkker i findRootBetween som programmeret i program 14.3. Gentagelsen bestyres af at funktionen kalder sig selv et tilstrækkeligt antal gange, indtil vi er tæt nok på roden.