コンピュータのプログラムにおいて， ある関数がその関数の内部で自分自身を呼び出して処理を進めていくこと．
例えば， n! （n の階乗）の値を求める関数を factorial(n) と命名すると， それは次のように定義できる．
これを適当なプログラミング言語で記述してコンピュータに実行してもらうと， 次のように処理が進んでいく．
まず，引数の n の値が 1 または 0 であるかどうかを判定する． もしそうならば， factorial(n) の値が 1 であることがわかり，処理は終了する． そうでなければ， n ・ factorial(n-1) の値を計算しようとする． しかし，この計算式の中に factorial( ・ ) が含まれているので， factorial(n) の定義の頭に戻って処理を続ける． ただし，引数の n の値を 1 だけ小さくする． そこで再び n の値が 1 か 0 になっているかの判定をして， そうならば 1 ， そうでなければ n の値を 1 だけ小さくして factorial(n) の 定義の頭へ…．
これを繰り返していくと，いずれ n の値が小さくなって 1 になり， factorial(n) の値が確定する． すると，その値は 1 つ前の factorial(n) の計算の部分に返される． 返えされた方は，その値を利用して n ・ factorial(n-1) の値を確定し， その値をやはり 1 つ前の処理に返す． これを繰り返して，戻るところがなくなれば， 最初に与えた n の値に対する factorial(n) の値が確定して， 処理が終了する．
まあ，いろいろと処理を続けていって，再び自分のところに帰ってくるから， 「再帰」というのだろう． 英語では“recursive call”という．
本編中では， 再帰呼び出し可能なプログラミング言語で記述できる世界は， そうでない言語で記述できる世界とは大きく違うと述べた． しかし，原理的には，前者で記述したアルゴリズムを 非再帰なアルゴリズムに変換することは可能である． 実際，コンピュータのハードを直接的に制御する機械語は 再帰的な記述を許さない． したがって， プログラミング言語で記述されたプログラムを機械語に翻訳してくれる コンパイラは， 再帰的に表現されたものを非再帰な手続きに変換する仕事もしているのである．
また，再帰呼び出しをすると， 今まで続けてきた処理をいったん中断して， 関数の頭に飛んでいってしまうので， 必要な値が確定した時点でその処理が継続できるように， 中断した時点の情報をどこかに保存しておく必要がある． したがって，繰り返し再帰呼び出しが起こると， そのたびに保存する情報量がどんどんと増えて， メモリを圧迫する． そのため，コンパイルに成功したプログラムでも， 実行時に“stack overflow”というメモリ管理上のエラーが出て， 動かなくなることがある．
再帰呼び出しが可能な言語はそうでないものよりも記述能力が高いが， コンピュータという「形」に執着しているかぎり， いろいろな限界があるのである．