Fibonacci Sayıları (Fibonacci Numbers)


Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde çok sık kullanılan sayı serileridir. Bu sayıların önemi özyineli (recursive) fonksiyonlar ile kolayca yazılabilmesidir.
Fibonacci serisinin ilk iki sayısı 1′dir. Diğer sayılar ise kendinden önceki iki sayının toplamıdır.
fib0=1
fib1=1
fib2=fib0 + fib1 = 1 + 1 = 2
fib3=fib1 + fib2 = 1 + 2 = 3
fib4=fib2 + fib3 = 2 + 3 = 5
…
bu işlemin kodu aşağıdaki şekilde yazılabilir:


int fibonacci(int n)

{
   if (0 == n) {
        return 0;
    } else if (1 == n) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

Yukarıda verilen bu recursive (kendi kendini çağıran) koda bakıldığında ve kodun tahlili yapıldığında aşağıdaki fonksiyon iç içe çağırma ağacı (recursion tree ) fark edilir:

fibonacci(4)
   +------------------------------
   |                             |
fibonacci(2)                 fibonacci(3)
   +-----------------            +---------------
   |                |            |              |
fibonacci(0)   fibonacci(1)  fibonacci(1)  fibonacci(2)
                                                +-----------
                                                |          |
                                           fibonacci(0) fibonacci(1)

yani yukarıdaki örnekte, fibonacci(4) fonksiyonu için çağırma işlemleri sırasıyla gösterilmiştir.

Fibonacci Serisini basan kod (ahmet Bey’in talebi üzerine ekliyorum)

Yukarıdaki kodlarda, verilen sıradaki fibonacci serisinin elemanını basan kodu yazmıştık. Şimdi verilen sayıya kadar olan bütün fibonacci sayılarını basan kodu yazmaya çalışalım.

Kodun çalışan hali aşağıdaki şekildedir:

Yukarıdaki kod dikkat edileceği üzere iteratif (döngü ile) yazılmış bir koddur. Şayet aynı işi özyineli (recursive) olarak yapmak istersek aşağıdaki problem ile karşılaşırız:

Yukarıdaki kodun çalışan hali:

Görüldüğü üzere 8. elemanı bastırmak için hesapladığımız bütün ara değerler ekrana bastırılıyor. Yani yukarıdaki recursion tree (özyineleme ağacının ) tamamı basılıyor. Bu durumda özyineli kodlamanın bu iş için uygun olmadığını söyleyebiliriz. Ancak yine de özyineli olarak fibonacci serisini basmakta ısrar edilirse aşağıdaki şekilde performansı hiçe sayan bir kod yazılabilir:

Yukarıdaki kodun çalışan hali aşağıdaki şekildedir:

Yukarıdaki bu yeni özyineli fonksiyonda her değer için tekrar ve tekrar fibonacci ağacı oluşturularak seri hesaplanmaktadır.


« Özyineli Fonksiyonlar (Recursive Functions)   |   Fibonacci Arama Algoritması (Fibonacci Search Algorithm) »



Yorumlar

Kullanıcı girişi yaparak ya da zorunlu olan * alanlarını doldurarak yorum yapabilirsiniz.

İsminiz *

Email adresiniz *

Web siteniz

Mesajınızı buraya yazabilirsiniz:

Toplam 2 yorum var.

  1. Fibonacci Arama Algoritması (Fibonacci Search Algorithm) : bilgisayar.kavramlari.com | 05 Aug 2008, 10:48

    [...] : Şadi Evren ŞEKER Bu arama algoritması, özyineli (recursive) bir seri olan fibonacci sayılarını kullanarak sıralı bir dizi üzerinde arama yapmaktadır. Çalışma mantığı arama yapılacak [...]

  2. ahmet | 08 Dec 2009, 12:40

    hocam fibonacci sayılarını fonksiyon olarak,nasıl cıkartırım?kullanıcıdan 5 girdiginde,1 1 2 3 5 cıktısı gibi

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Fibonacci Sayıları (Fibonacci Numbers)' isimli yazı 05 Aug 2008 tarihinde, saat: 10:19 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 1735 defa okunmuştur.

Benzer yazıları Bilgisayar Matematiği kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.


Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar
Yapılan Son Yorumlar
Yakın Yazılar
Bağlantılar