C programlama

C Dilinde Rekürsif Fonksiyonlar

image_pdfimage_print

Kendisini çağırabilen işlevlere rekürsif (özyineli) işlev denir.

Bazı algoritmalar kendiliğinden rekürsiftir. Bunlardan en bilinenide faktöriyel algoritmasıdır. Matematikte, n sayısının faktöriyeli

n!=1.2.3……(n-1).n

şeklinde 1’den n ‘e kadar tam sayıların çarpımı biçimindedir. Ayrıca 0!=1 olarak tanımlanmıştır.

Şimdi yukarıdaki ifadeyi

n!=1.2.3……n=F(n) biçiminde tanımlarsak bu durumda

(n-1)!=1.2.3..(n-1)=F(n-1) olarak yazabiliriz. Buna göre

(n-1)!=1.2.3..n=F(n)=1.2.3…(n-1).n=F(n-1).n    ifadesine ulaşılacaktır. Bu durumda F(n)=F(n-1).n

İfadesi rekürsif bir ifadedir. Çünkü F(n) fonksiyonunun tanımlanması ve hesabı fonksiyonun kendisine referans verilerek gerçekleştirilmektedir.

Şimdi, yukarıdaki tanımlamaya göre hesaplamanın nasıl yapıldığına bakalım. Örnek olarak n=4 olsun.

Bu durumda, n=4 için

  1. F(4)=F(3).4
  2. F(3)=F(2).3
  3. F(2)=F(1).2
  4. F(1)=F(0).1

Adımları gerekecektir. Şimdi f(0)=0!=1 olarak tanımlı değere ulaşıldığı için 4. Adımda F(1)=1 olarak hesaplanabilir. Sonra bir önceki adıma geçilerek F(2)=1.2=2 olarak hesaplanır. Sonra 2. Adıma dönülecek F(3)=3.2=6 olarak hesaplanacaktır. Sonuçta ise 1. Adıma dönülerek F(4)=6.4=24 olarak 4! İfadesinin sonucu bulunacaktır.

Böylelikle rekürsif bir algoritmada iki kısım mevcuttur.

  1. Argümanın bir veya daha fazla değeri için fonksiyon değerinin belirlenmiş olduğu durum. Örnek olarak yukarıdaki algoritmada F(0)=0!=1 durumu. Bu durumada baz adı verilir.
  2. İndüktif veya rekürsif adım. Yukarıdaki örnekte

F(n)=F(n-1).n durumu

Örnek:

C dilinde rekürsif faktöriyel program

Programın çıktısı

Fibonacci Sayılarının Üretilmesi

Fibonacci dizisi 1,1,2,3,5,8,13,21,34,55,89,144,233….. biçiminde tanımlanmış sonsuz dizidir.

F0=1 ve F1=1 alınarak

F2=F0+F1

F3=F1+F2

Ve genel olarak

Fi= Fi-1 +Fi-2 biçiminde tanımlanır.  Fibonacci dizisini hesaplayan rekürsif bir C fonksiyonu örneği yapalım.

Örnek:

Programın çıktısı

 

 

0
0

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir