Relasi rekurensi dan fungsi rekursif

Barisan dapat didefinisikan dengan dua cara. Rumus tertutup menghitung suku ke-n langsung dari n, misalnya aₙ = 2n + 1. Definisi rekursif terdiri atas relasi rekurensi, yaitu persamaan yang menyatakan sebuah suku dari suku-suku sebelumnya, dan kondisi awal, yaitu satu atau beberapa suku pertama. Tanpa kondisi awal, relasi rekurensi tidak menentukan barisan apa pun. Definisi rekursif muncul di mana pun keadaan hari ini dihitung dari keadaan kemarin: saldo tabungan, jumlah langkah algoritma, atau banyaknya cara menyusun sesuatu yang dibangun dari susunan yang lebih kecil.

Contoh: a₁ = 3 dan aₙ = 2aₙ₋₁ + 1. Suku-sukunya dihitung satu per satu: a₂ = 2 × 3 + 1 = 7, a₃ = 2 × 7 + 1 = 15, a₄ = 2 × 15 + 1 = 31. Barisan Fibonacci memakai dua suku sebelumnya: F₀ = 0, F₁ = 1, dan Fₙ = Fₙ₋₁ + Fₙ₋₂. Di Python, definisi rekursif ditulis sebagai fungsi yang memanggil dirinya sendiri. Kondisi awal menjadi kasus dasar, yaitu cabang yang langsung mengembalikan nilai tanpa memanggil diri lagi. Pemanggilan yang sama bisa terjadi berulang kali, dan dekorator functools.lru_cache menyimpan hasil yang sudah dihitung sehingga tidak dihitung ulang.

def suku(n):
    if n == 1:          # kasus dasar = kondisi awal
        return 3
    return 2 * suku(n - 1) + 1

print([suku(n) for n in range(1, 5)])   # [3, 7, 15, 31]