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, czylistał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. Najczęściej używa się takich drzew 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 nieposiadają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ę.