Drzewo wywołań funkcji

Drzewo wywołań funkcji (ang. call tree) to drzewo przedstawiające proces obliczania wartości wyrażenia. Liście drzewa wywołań zawierają niepodzielne części wyrażenia, czyli stałe i zmienne. Węzły wewnętrzne i korzeń odpowiadają wywołaniu funkcji (lub operatorów) z argumentami obliczonymi przez ich poddrzewa.

Drzewa wywołań rozpatruje się przede wszystkim w konstrukcji kompilatorów języków programowania, ale także w analizie programów (ang. program analysis), oraz w konstrukcji i analizie algorytmów. Zwykle rozpatruje się drzewa wywołań dla wyrażeń, które zawierają wywołania funkcji, lub drzewa dla obliczania wartości funkcji rekurencyjnych.

W typowych językach programowania, wyrażenia mogą generować skutki uboczne. Zazwyczaj drzewo wywołań nie uwzględnia tego faktu i obrazuje jedynie strukturę obliczania. Szczególnie interesujące są drzewa wywołań dla funkcji rekurencyjnych nie posiadających skutków ubocznych. Drzewa takie można przekształcić zwykłymi metodami matematycznymi (zob. np. programowanie dynamiczne) w skierowany graf acykliczny (DAG), co umożliwia optymalizację.

Jako przykład rozważmy drzewo wywołań dla funkcji ${\displaystyle F}$ obliczającej wartość n-tego wyrazu ciągu Fibonacciego:

 fun F (n :int) :int = 
     if n=1 or n=2 then 1
     else F (n-1) + F (n-2)

Diagram po prawej stronie prezentuje drzewo wywołań dla wyrażenia ${\displaystyle F(6)}$. Dla uproszczenia pominięto na nim wartości wyrażeń pośrednich, pokazując jedynie wywołania funkcji). Łatwo zauważyć, że drzewo to zawiera wiele zbędnych obliczeń, na przykład ${\displaystyle F(2)}$ jest obliczane pięciokrotnie a ${\displaystyle F(3)}$ trzykrotnie, po mimo to, że wartość tej funkcji dla zadanych parametrów jest zawsze taka sama.

Kolejny diagram pokazuje jak powyższe drzewo może zostać zredukowane do grafu skierowanego za pomocą technik typu programowanie dynamiczne lub memoizacja.