Section courante

A propos

Section administrative du site

La fabuleuse fonction d'«Ackermann» de 1926, laquelle, lorsqu'on met des chiffres de plus en plus gros dans le premier paramètre, augmente beaucoup plus vite que l'exponentiel! Sa formule est cité dans presque tous les livres de récursivité, mais paradoxalement, son nom, Wilhelm Ackermann, est difficile à trouver! Voici un code source Ada effectuant le calcul de la fonction d'«Ackermann» dans ses positions inférieures:

  1. WITH TEXT_IO;
  2.  
  3. PROCEDURE AckermannExample IS 
  4.    
  5.    USE TEXT_IO;
  6.    
  7.    FUNCTION Ackermann(M,N:IN Integer) RETURN Integer IS BEGIN
  8.       IF M = 0 THEN         
  9.          RETURN N + 1;
  10.       ELSE         
  11.          IF N = 0 THEN 
  12.             RETURN Ackermann(M-1,1);
  13.          ELSE 
  14.             RETURN Ackermann(M-1,(Ackermann(M,N-1)));
  15.          END IF;
  16.       END IF;
  17.    END Ackermann; 
  18.    
  19. BEGIN
  20.    FOR I IN 1..2 LOOP      
  21.       FOR J IN 1..10 LOOP         
  22.          PUT_LINE("Ackermann(" & INTEGER'IMAGE(I) & "," & INTEGER'IMAGE(J) & "=" & INTEGER'IMAGE(Ackermann(I, J)));        
  23.       END LOOP;      
  24.    END LOOP;    
  25. END AckermannExample;

on obtiendra le résultat suivant :

Ackermann( 1, 1)= 3
Ackermann( 1, 2)= 4
Ackermann( 1, 3)= 5
Ackermann( 1, 4)= 6
Ackermann( 1, 5)= 7
Ackermann( 1, 6)= 8
Ackermann( 1, 7)= 9
Ackermann( 1, 8)= 10
Ackermann( 1, 9)= 11
Ackermann( 1, 10)= 12
Ackermann( 2, 1)= 5
Ackermann( 2, 2)= 7
Ackermann( 2, 3)= 9
Ackermann( 2, 4)= 11
Ackermann( 2, 5)= 13
Ackermann( 2, 6)= 15
Ackermann( 2, 7)= 17
Ackermann( 2, 8)= 19
Ackermann( 2, 9)= 21
Ackermann( 2, 10)= 23

Voir également

Science - Mathématique

Dernière mise à jour : Samedi, le 25 août 2012