Rekursi

Rekursi berhubungan dengan, tetapi tidak sama, suatu referensi dalam spesifikasi prosedur sampai pada eksekusi beberapa prosedur lainnya.
Misalnya, suatu resep bisa mengacu pada memasak sayuran, yang merupakan prosedur yang kemudian membutuhkan memanaskan air, dan seterusnya.
Namun, prosedur rekursif adalah spesial dengan (paling tidak) salah satu langkahnya memanggil instansi baru dari prosedur yang sama, seperti suatu resep gandum hitam menggunakan beberapa sisa adonan dari resep yang sama yang telah dibuat.
Hal ini tentu saja membuat suatu kemungkinan perulangan tanpa berakhir; rekursi hanya dapat digunakan secara tepat dalam definisi jika langkah yang bersangkutan dilewat pada beberapa kasus sehingga prosedur dapat selesai, seperti resep gandum-hitam yang memberitahu anda bagaimana membuat adonan awal seandainya anda belum pernah membuatnya sebelumnya.
Bahkan jika didefinisikan secara tepat, prosedur rekursif tidak mudah dilakukan oleh manusia, karena ia membutuhkan membedakan pemanggilan prosedur yang baru dengan yang lama (yang telah dieksekusi sebagian); hal ini membutuhkan beberapa administrasi sejauh mana berbagai prosedur instan yang berjalan bersamaan telah berjalan.
Karena hal ini definisi rekursif sangat jarang dalam keadaan harian.
Contohnya dapat berupa prosedur untuk menemukan jalan melewati sebuah labirin.
Terus ke depan sampai menemui jalan keluar atau titik percabangan (sebuah titik mati dianggap sebagai sebuah titik percabangan dengan 0 cabang).
Jika titik yang ditemui adalah suatu jalan keluar,berhenti.
Kalau tidak coba setiap cabang bergantian, menggunakan prosedur secara rekursif; jika setiap percobaan gagal karena mencapai titik mati, kembali ke jalur yang menyebabkan titik percabangan dan laporkan kegagalan.
Apakah ini tepat mendefinisikan suatu prosedur pemberhentian bergantung kepada bentuk labirinnya: ia tidak membolehkan perulangan.
Dalam semua kasus, mengeksekusi prosedur membutuhkan pencatatan teliti semua titik percabangan yang telah dieksplorasi, dan cabang-cabang mana yang telah dicoba..