L'espace caché de la récursivité

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 10 — Prouver et analyser : la boîte à outils formalisée

Énoncé

Analyser la complexité temporelle et spatiale de la recherche dichotomique récursive dichotomie_rec(v, t, g, d).

Temps : $O (lo g n)$ . À chaque appel récursif, la taille de l'intervalle à traiter est divisée par 2.
Espace : $O (lo g n)$ . Bien qu'aucune structure de données auxiliaire ne soit allouée en cours d'exécution, la pile d'appels système doit stocker les contextes de chaque appel en attente. La profondeur maximale de récursion étant en $lo g_{2} (n) + 2$ , la complexité spatiale auxiliaire est logarithmique.

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.