RECURSİF HESAPLANMASI

-----------------------Algoritma Analizi Recursif ifadeler------------------

RECURSİF HESAPLANMASI

Resürsif algoritması eğer bilgisayarımızn işlemci güçü iyi ise çok  iyi sonuçlar vermektedir eğer işlemcimiz normal ve biz recursif ifade kullandığımızda inanılmaz bir şekilde bilgisayarın ısınmasına sebeb olacak çünkü recursif ifadeler kendi kendini çağıran metotlardan oluşmaktadır aslında recursif ifadeler kod yazarken  kod yazmamız daha kolay oluyor iteratife göre ancak bazen recursif ifade de çalışmak zor ve karmaşıktır örneğin gezign satıc örneğinde olduğu gibi bunun notasyonu O(2^n) karmaşıklığına sahiptir bu da çok işelm gerektirir işte bunun gibi algoritmalarda recursif yazılmış bir ifadeninin iteratife çevirip oradan da sonuca ulaşmak çok kolaydır

Bu fonksiyonlara örnek olarak faktöriyel fonksiyon, Fibonacci dizisi örnek verebiliriz

Basit bir örnek vereyim; 3,  6,  12,  24,  48,  …

Görüldüğü gibi 3 ile başlayan ve bir sonraki terimi bir önceki teriminin 2 katı olan bir dizidir

Recursif ifade olmazsa olmaz kural bir başlangıç belirlemek (initial condition) ve kendi kendisini çağıran fonksiyon kullanmak ve bunu fonksiyo olarak yazarsak;

Bu dizi rekürsif olarak   şeklinde ya da  şeklinde tanımlanabilir. Yani bir önceki terimi hesaplamadan  terim  formülü ile hesaplanabilir.

NOT: Kaçıncı derecede ise o kadar başlangıçı olmalıdır

Birkaç bağıntı örneği verelim ;

Verilen yinelemeli bağıntı ikinci dereceden sabit katsayılara sahiptir ama homojen değildir (n² yüzünden). Ve  a₁ = 1 ve a₂ = 2 başlangıç değerleri için a₃₌₁₅ ve a₄₌₆₈  elde etmekteyiz

Bu yinelemeli bağıntı doğrusal olmayan bir bağıntıdır (a_n-1a_n-2 çarpım durumunda olduğu için). a₁ = 1 ve a₂ = 2 başlangıç değerleri için a₃ ve a₄ sırasıyla 13 ve 68 olarak elde edilebilir.

Bu yinelemeli bağıntı homojen ikinci dereceden bir bağıntıdır. Fakat sabit katsayılara sahip değildir (çünkü a_n-1 in katsayısı n dir. Bir sabit değildir). a₁ = 1 ve a₂ = 2 başlangıç değerleri için a₃ ve a₄ sırasıyla 9 ve 42 olarak elde edilebilir.

Yukarıda verilen yinelemeli bağıntı üçüncü dereceden sabit katsayıları olan bir bağıntıdır. Dolayısıyla 3 farklı başlangıç durumuna ihtiyacımız vardır. Örneğin a₁ = 1 ve a₂ = 2 ve a₃ = 1 başlangıç değerleri için a₄, a₅  ve a₆  sırasıyla 6 , -37 ve 254 olarak elde edilebilir.

İkinci Dereceden Homojen Doğrusal Yinelemeli Bağıntıların Çözümü

Homojen ikinci dereceden ve sabit katsayılara sahip bir bağıntı aşağıda verilen forma sahiptir:

 ya da

Yukarıda verilen ifade de s ve t 0’dan farklı sabitleri simgelemektedir. Biz aşağıda verilen ikinci dereceden bir polinomu yukarıda verilen yinelemeli bağıntı ile ilişkilendirebiliriz:

 polinomuna yinelemeli bağıntının karakteristik polinomu ve bu polinomun köklerine de onun karakteristik kökleri adı verilir.

Teorem. şeklindeki yinelemeli bir bağıntının karakteristik polinomu  şeklinde ve bu bağıntı r₁ ve r₂ şeklinde iki köke sahip ise o zaman yinelemeli bağıntının genel çözümü aşağıdaki gibi verilebilir:

Genel çözümdeki c₁ ve c₂ katsayıları başlangıç durumlarından elde edilebilir. Teorem kökler gerçek olmadığı durumlar için de geçerlidir.

Örnek . yineleme bağıntısının genel çözümünü elde ederek a₀ = 1 ve a₁ = 2 başlangıç durumları için bu genel çözümdeki katsayıları da elde ediniz.

Cevap. polinomunu verilen yinelemeli bağıntı için elde edebiliriz.  Dolayısıyla bu polinomun köklerini de r₁= 3 ve r₂= -1 şeklinde elde edebiliriz. Yine verilen teorem gereği bu yinelemeli bağıntının genel çözümünü de

 elde edilebilir. Daha sonra;

n = 0 ve a₀ =1 için ya da

n = 1 ve a₁ = 2 için ya da

Verilen denklemlerden de  ve olarak elde edilir. Sonuç olarak verilen başlangıç durumları için yinelemeli bağıntının tek çözümü şeklinde bulunur.