よく知られた事実ですが、指数的な回数の再帰呼び出しが行われるため、実用的ではありません。
フィボナッチ数列を計算する再帰関数は再帰の仕方がわかりやすいですが、よくわからない再帰の仕方の関数の場合はどうでしょうか？
関数が呼ばれたときにデバッグプリントをする方法では、どのような再帰構造で呼ばれたのかわかりません。
再帰深度だけインデントしてデバッグプリントすればよいのですが、インデント量を保持する必要があります。
一つの方法は、再帰関数に、再帰深度を受け取る引数を追加する方法です。その引数には、外部から呼び出す場合は0を、再帰呼び出しをする場合は、引数の値+1を、それぞれ渡します。 この方法の欠点は、関数原型を変更する必要があるです。また、相互再帰の場合は関係するすべての関数の関数原型を変更する必要があります。
もう一つの方法は、グローバル変数に再帰深度を保存する方法です。関数の先頭でその変数をインクリメントし、return文の直前でその変数をデクリメントします。
自己再帰関数であれば、グローバル変数とせず、関数内static変数とすることもできます。
この方法の欠点は、大域脱出されるとデクリメントする機会を失い、値が永久に狂ってしまう点です。
前者は再帰段数に比例する記憶領域を消費するのに対し、後者は定数の記憶領域しか消費していません*1。 これは不思議な感じがありますが、（末尾再帰ではない場合）後者でも再帰段数に比例するコールスタックが消費されていることを合わせて考えると、定数倍の違いになっています。
後者の方法の空間効率が良いのは、「デクリメントすれば元に戻る」、つまり逆操作が存在するという部分が重要です。 木を走査しながら演算を繰り返していき、葉での値を求める、といった場合、一般に逆演算があるとは限りません。 逆演算がない場合、後者のような方法はとれず、前者のような方法を採用することになります。
なお、もともとが末尾再帰だった場合、後者の方法は末尾再帰ではなくしてしまう効果があります。 つまり、先ほどとは逆に、前者の方法は定数の記憶領域のみを消費し、後者の方法は（コールスタック用に）再帰段数に比例する記憶領域を消費することになります。 ただし、コールスタックに積まれる情報は毎回同じものなので、後者の方法の場合でも本質的には圧縮可能です。
