C Dilinde Özyineli (Rekürsif) Fonksiyonlar

 

Daha önce C dilinde fonksiyon kavramını görmüştük. Objective-C dilinde bir fonksiyon başka bir fonksiyonu ya da fonksiyonlar grubunu çağırabilir. Objective-C dilinde bundan daha ilerisi de mümkündür. Bir fonksiyon kendisini de çağırabilir. Kendisini çağırabilen fonksiyonlara özyineli (rekürsif, İng. recursive) fonksiyon adı verilir.

Bazı algoritmalar, doğaları gereği özyinelidir. En çok bilinen özyineli algoritmalardan biri de faktöryel algoritmasıdır. Matematikte n sayısının faktöryeli,

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

şeklinde, 1’den n’e kadar tam sayıların çarpımı şeklinde tanımlanır. Ayrıca 0!=1 olarak tanımlanmıştır. Şimdi yukarıdaki ifadeyi,

n!=1.2.3....n=F(n)

şeklinde tanımlarsak bu durumda,

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

olarak yazılabilir. Buna göre,

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

ifadesine erişilecektir. Bu durumda,

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

ifadesi özyineli bir ifadedir; çünkü F(n) fonksiyonunun tanımlanması ve hesabı, fonksiyonun kendisine referans verilerek gerçekleştirilir.

Şimdi, yukarıdaki tanımlamaya göre hesaplamanın nasıl yapılabileceğine bakalım. Örnek bir durum olarak, n=4 durumunu ele alalım. Böylece, n=4 için,

I.  F(4)=F(3).4

II.  F(3)=F(2).3

III.  F(2)=F(1).2

IV.  F(0)=F(0).1

adımları gerekecektir. F(0)=0!=1 olarak tanımlı bir değere ulaşıldığından, IV. adımda, F(1)=1 olarak hesaplanabilir. 

Sonra bir önceki adıma geçilerek, F(2)=1.2 =2 olarak hesaplanır.

Daha sonra II. adıma dönülecek ve F(3)=2.3=6 olarak hesaplanır.

Sonuçta ise I’e dönülerek F(4)=6.4=24 olarak 4! ifadesinin sonucu bulunacaktır.

 

Özyineli bir algoritmada, iki kısım mevcuttur:

I) Argümanın bir veya daha fazla değeri için, fonksiyon değerinin belirlenmiş olduğu durum. Örneğin, yukarıdaki gibi bir algoritmada F(0)=0!=1 durumu söz konusuysa, buna baz adını veriyoruz.

II) İndüktif (İng.inductive) veya rekürsif (recursive) adım. Yukarıdaki örnekte,

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

 

OBJECTIVE-C DİLİNDE REKÜRSİF FAKTÖRİYEL PROGRAMININ LİSTESİ:

 

#import <Foundation/Foundation.h>
 
int fakt(int);
 
int main(int argc,const char *argv[])
{
    NSAutoreleasePool *pool=[[NSAutoreleasePool alloc] init];
    
    int k;
    NSLog(@"\n Faktoryeli hesaplanacak sayiyi giriniz...\n");
    scanf("%i",&k);
    if (k<0)
        NSLog(@"\nSAYI NEGATİF OLAMAZ");
    else
        NSLog(@"\n%i=%i    ",k,fakt(k));
    [pool drain];
    return 0;
}

int fakt(int n)
{
    if(n<=1)
        return (1);
    else
        return (n*fakt(n-1));
}

 

REKÜRSİF FAKTÖRİYEL PROGRAMININ ÇIKTISI:

Faktoryeli hesaplanacak sayiyi giriniz...
5
5=120

 

---

FIBONACCI SAYILARININ ÜRETİLMESİ

Fibonacci dizisi,

            1,1,2,3,5,8,13,21,34,55,89,144,233,..

şeklinde tanımlanmış bir sonsuz dizidir. Burada,

              F₀=1   ve F₁=1  alınarak

              F₂=F₀+F₁

             F₃=F₁+F₂

ve genel olarak

        F_i=F_i-1+F_i-2

şeklinde tanımlanır.

 

Aşağıda,Fibonacci dizisini hesaplayan rekürsif bir C fonksiyonu, bunu çağıran ana program ile birlikte sunulmaktadır:

FIBONACCI SAYILARINI HESAPLAYAN REKÜRSİF BİR OBJECTIVE C FONKSİYONU

int fibon(int );
#import <Foundation/Foundation.h>

int main(int argc,const char *argv[])
{
    NSAutoreleasePool *pool=[[NSAutoreleasePool alloc] init];
    
    int k,i;
    NSLog(@"\n UST LIMIT..\n");
    scanf("%i",&k);
    if (k<=0)
        NSLog(@"\nSAYI SIFIR YA DA NEGATİF OLAMAZ");
    else
    {
        for (i=1; i<=k; i++)
            NSLog(@"\n%i ",fibon(i));
    }
}

int fibon(int n)
{
    if(n==1 || n==2)
        return (1);
    else
        return (fibon(n-1)+fibon(n-2));
}

 

FIBONACCI PROGRAMININ ÇIKTISI:

UST LIMIT...
4

1
2
3

 

---

ÜS ALMA İŞLEMİNİ GERÇEKLEŞTİREN REKÜRSİF BİR OBJECTIVE C FONKSİYONU

Objective C’de  pow(x,y) fonksiyonunun  x^y işlemini gerçekleştirdiğini biliyorsunuz. Bu fonksiyonun gerçekleştirdiği işlevi gerçekleştiren us adlı rekürsif bir Objective C fonksiyonu geliştireceğiz.

x>0 ise, x^y fonksiyonu

                                      x^y-1.x

şeklinde hesaplanır.

ÜS ALMA İŞLEMİNİ GERÇEKLEŞTİREN REKÜRSİF OBJECTIVE C FONKSİYONU VE BU FONKSİYONU ÇAĞIRAN ANA PROGRAMIN LİSTESİ:

 

#import <Foundation/Foundation.h>

float us(float x,int y)
{
    if (x==0)
        return(1);
    if (x>0 && y==0)
        return(1);
    if (x>0 && y==1)
        return(x);
    if (x>0 && y>1)
        return(us(x,(y-1))*x);
    return 0;
}

int main(int argc, char* argv[])
{
    int n;
    float x;
    NSLog(@"\n TABAN(x degeri.).\n");
    scanf("%f",&x);
    NSLog(@"\n US(y değeri)..\n");
    scanf("%i",&n);
    NSLog(@"\nSONUC=%12.2f  ",us(x,n));   
}

 

ÜS ALMA PROGRAMININ ÇIKTISI:

TABAN(x degeri.).
2
US(y değeri)..
3
SONUC=        8.00