Bagaimana cara menulis 2 ** n - 1 sebagai fungsi rekursif?

Saya membutuhkan fungsi yang mengambil n dan mengembalikan 2 ⁿ - 1 . Kedengarannya cukup sederhana, tetapi fungsinya harus bersifat rekursif. Sejauh ini saya hanya punya 2 ⁿ :

def required_steps(n):
    if n == 0:
        return 1
    return 2 * req_steps(n-1)

Latihan menyatakan: "Anda dapat mengasumsikan bahwa parameter n selalu bilangan bulat positif dan lebih besar dari 0"

2**n -1juga 1 + 2 + 4 + ... + 2 ^n-1 yang dapat dibuat menjadi fungsi rekursif tunggal (tanpa yang kedua untuk mengurangi 1 dari kekuatan 2).

Petunjuk : 1 + 2 * (1 + 2 * (...))

Solusi di bawah, jangan lihat jika Anda ingin mencoba petunjuk itu terlebih dahulu.

Ini berfungsi jika ndijamin lebih besar dari nol (seperti yang dijanjikan dalam pernyataan masalah):

def required_steps(n):
    if n == 1: # changed because we need one less going down
        return 1
    return 1 + 2 * required_steps(n-1)

Versi yang lebih kuat akan menangani nilai nol dan negatif juga:

def required_steps(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 0
    return 1 + 2 * required_steps(n-1)

(Menambahkan cek untuk non-integer dibiarkan sebagai latihan.)

Untuk memecahkan masalah dengan pendekatan rekursif Anda harus mengetahui bagaimana Anda dapat mendefinisikan fungsi dengan input yang diberikan dalam hal fungsi yang sama dengan input yang berbeda. Dalam hal ini, karena f(n) = 2 * f(n - 1) + 1, Anda dapat melakukan:

def required_steps(n):
    return n and 2 * required_steps(n - 1) + 1

maka:

for i in range(5):
    print(required_steps(i))

output:

0
1
3
7
15

Anda dapat mengekstrak bagian yang sangat rekursif ke fungsi lain

def f(n):
    return required_steps(n) - 1

Atau Anda dapat mengatur bendera dan menentukan kapan harus mengurangi

def required_steps(n, sub=True):
    if n == 0: return 1
    return 2 * required_steps(n-1, False) - sub

>>> print(required_steps(10))
1023

Menggunakan parameter tambahan untuk hasilnya, r-

def required_steps (n = 0, r = 1):
  if n == 0:
    return r - 1
  else:
    return required_steps(n - 1, r * 2)

for x in range(6):
  print(f"f({x}) = {required_steps(x)}")

# f(0) = 0
# f(1) = 1
# f(2) = 3
# f(3) = 7
# f(4) = 15
# f(5) = 31

Anda juga dapat menulisnya menggunakan shift kiri bitwise, <<-

def required_steps (n = 0, r = 1):
  if n == 0:
    return r - 1
  else:
    return required_steps(n - 1, r << 1)

Outputnya sama

Mintalah pengganti untuk mengingat nilai asli dari n dan kemudian untuk langkah pertama yaitu n == N, kembali2^n-1

n = 10
# constant to hold initial value of n
N = n
def required_steps(n, N):
    if n == 0:
        return 1
    elif n == N:
        return 2 * required_steps(n-1, N) - 1
    return 2 * required_steps(n-1, N)

required_steps(n, N)

Salah satu cara untuk mendapatkan offset "-1" adalah menerapkannya sebagai imbalan dari panggilan fungsi pertama menggunakan argumen dengan nilai default, lalu secara eksplisit mengatur argumen offset ke nol selama panggilan rekursif.

def required_steps(n, offset = -1):
    if n == 0:
        return 1
    return offset + 2 * required_steps(n-1,0)

Di atas semua jawaban luar biasa yang diberikan sebelumnya, di bawah ini akan menunjukkan implementasinya dengan fungsi internal.

def outer(n):
    k=n
    def p(n):
        if n==1:
            return 2
        if n==k:
            return 2*p(n-1)-1
        return 2*p(n-1)
    return p(n)

n=5
print(outer(n))

Pada dasarnya, ini memberikan nilai global n ke k dan mengulanginya dengan perbandingan yang sesuai.