Funcția Ackermann

Aspecte teoretice:

Funcția lui Ackermann este definită de următoarele relații:

ack(m,n) = ack(m-1, ack(m, n-1)); ack(0,n) = n+1; ack(m,0) = ack(m-1,1);

Această funcție are o adâncime mare din punctul de vedere al recursivității. Este utilă în compararea eficienței compilatoarelor limbajelor de programare. De asemenea valoarea ei crește foarte rapid.

Să determinăm A(2,2). Vom aplica succesiv definiția până la identificarea unor argumente pentru care valoarea funcției A se poate calcula. Apoi vom substitui valoarea calculată în locul celui mai interior argument de pe poziția a doua, după care vom relua aplicarea definiției, dacă numele funcției nu mai apare. Avem succesiv:
A(2,2)=A(1,A(2,1))=A(1,A(1,A(2,0)))=A(1,A(1,A(1,1)))=A(1,A(1,A(0,A(1,0))))=A(1,A(1,A(0,A(
0,1))))=A(1,A(1,A(0,2)))=A(1,A(1,3))=A(1,A(0,A(1,2)))=A(1,A(0,A(0,A(1,1))))=A(1,A(0,A(0,A
(0,A(1,0)))))=A(1,A(0,A(0,A(0,A(0,1)))))=A(1,A(0,A(0,A(0,2))))=A(1,A(0,A(0,3)))=A(1,A(0,4
))=A(1,5)=A(0,A(1,4))=A(0,A(0,A(1,3)))=A(0,A(0,A(0,A(1,2))))=A(0,A(0,A(0,A(0,A(1,1)))))=A
(0,A(0,A(0,A(0,A(0,A(1,0))))))=A(0,A(0,A(0,A(0,A(0,A(0,1))))))=A(0,A(0,A(0,A(0,A(0,2)))))
=A(0,A(0,A(0,A(0,3))))=A(0,A(0,A(0,4)))=A(0,A(0,5))=A(0,6)=7.

Cod Sursa C++

 

#include "stdafx.h"
#include<iostream>
 
using namespace std;
 
long ack(unsigned x, unsigned y)
{
	if (x == 0) return y + 1;
	if (y == 0) return ack(x - 1, 1);
	return ack(x - 1, ack(x, y - 1));
}
 
void main()
{
	unsigned m, n;
	cout << "m="; cin >> m;
	cout << "n="; cin >> n;
	cout << ack(m, n);
	cout << endl;
	system("Pause");
}

Cod Sursa C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace AckermannCS
{
    class Program
    {
        static long ack(long x, long y)
        {
            if (x == 0) 
                return y + 1;
            if (y == 0) 
                return ack(x - 1, 1);
            return 
                ack(x - 1, ack(x, y - 1));
        }
        static void Main(string[] args)
        {
            long m, n;
            Console.Write("m= ");
            m = Convert.ToInt32(Console.ReadLine());
            Console.Write("n= ");
            n = Convert.ToInt32(Console.ReadLine());
            Console.Write(ack(m, n));
            Console.WriteLine();
            Console.ReadKey();
        }
    }
}

Cod Sursa VB

Module Module1
 
    Private Function ack(x As Long, y As Long) As Long
        If x = 0 Then
            Return y + 1
        End If
        If y = 0 Then
            Return ack(x - 1, 1)
        End If
        Return ack(x - 1, ack(x, y - 1))
    End Function
    Sub Main(args As String())
        Dim m As Long, n As Long
        Console.Write("m= ")
        m = Convert.ToInt32(Console.ReadLine())
        Console.Write("n= ")
        n = Convert.ToInt32(Console.ReadLine())
        Console.Write(ack(m, n))
        Console.WriteLine()
        Console.ReadKey()
    End Sub
 
End Module

Cod Sursa LISP

 

(defun ackermann (m n) “The Ackermann Function”
(cond ((= m 0) (+ n 1))
((= m 1) (+ n 2))
((= m 2) (+ 3 (* n 2)))
((= m 3) (+ 5 (* 8 (- (expt 2 n) 1))))
(t (cond ((= n 0) (ackermann (- m 1) 1))
(t (ackermann (- m 1) (ackermann m (- n 1))))
))
))

Cod Sursa Haskell

g :: Integer -> Integer -> Integer
g 0 x = x + 1
g n 0 = g (n -1) 1
g n x = g (n-1) (g n (x-1))

Rezultat: