Drzewo wywołań funkcji

Szablon:DoWeryfikacji 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ę. Szablon:Informatyka stub