Recursive Fonksiyonlar ve Recursive Fonksiyonların Analizi
Her şeyden önce bu benim nerdeyse ciddi ciddi oturup yazdığım ilk yazı. Bu yüzden, yok İngilizce yok Türkçe, arada kaynayacak anlamadığınız bir şey olursa artık yapacak bir şey yok.
Her şeyden önce herhangi bir programlama dilindeki fonksiyonların normal lise matematiğindeki fonksiyonlardan hiç bir farkı yoktur. Fonksiyonun tanımını bir kutu olarak düşünürsek bu kutudan çıkacak değerler ya da o kutuda inputlara uygulanacak metotlar kutunun içine yani fonksiyona bakar. Bir iterative fonksiyonu normal f(x) = 8x gibi bir fonksiyon olarak tanımlayabiliriz.
Bir kısa örnek görelim:
public int ItFunction(int x)
{
return x*8;
}
Burda normal bir algoritma analizi yaparsak görüldüğü gibi ?(1) dir.
Lisedeyken de karşımıza genelde matematik sınavlarında çıkan soru tarzı ise
f(x) = f(x -1) + 1 :
f(2) = 1 ise f(10) = ? gibi sorular karşımıza çıkmıştır.
İşte bu tip fonksiyonların bilgisayar programlamasında adı ise recursive fonksiyonlardır yani
bir fonksiyon kendini çağırıyorsa recursive olur (Recurssion for dummies gibi oldu ama ne yapalım herkes anlasın)
Recursive fonksiyonların kodlarını vermeden önce biraz complexity sinden bahsedelim yani algoritma analizi yapalım. Her yerde olan ve merge sort üzerinden anlatılan recursive fonksiyonları ben Fibonacci sayıları üzerinden anlatmayı tercih edeceğim.
Fibonacci sayılar bir sayı kendinden önce gelen iki sayının toplamdır diye tanımlanır
O zaman Fib(x) = Fib(x -1) + Fib(x -2) şeklinde yazabiliriz
Recursive fonksiyonların analizini yapmak 3 tane yöntem vardır Bunlar substitution , recurssion tree ve master method lardır. En kolay ve gözde hemen canlanacak olan recursion tree olduğu için hemen bu fonksiyonun recursion tree sini yapalım.
Yukarıdaki tree ye bakarsak her bir fonksiyon kendini 1 e kadar tekrar edeceğini anlarız
n gibi bir sayı verirsek yüksekliğinin de n olacağını kestirebiliriz sonuçta 1 e kadar gideceğine göre ve her bir fonksiyon ?(1) lik bir yaptığından en alt satırda da n tane olduğundan O(n^2) diye fonksiyonun karmaşıklığını hesaplarız.
Bunun için daha iyi olduğunu düşüneceğim MIT Press An Introduction to Algorithms kitabından bir örnek vermek gerekirse:
Neyse şimdilik biraz kod yazma sırası
Hemen Fibonacci fonksiyonunu verelim
public int Fibonacci(int x)
{
if (x == 1 || x == 0)
return 1;
return Fibonacci(x - 1) + Fibonacci(x - 2);
}
Bu da microsoft ta sorulan sorulardan biri bir string in reverse edilmesi için recursive fonksyion yazınız hemen c# kodunu verelim
public string Reverse(string Data, int Length)
{
if (Length == 0)
{
return "";
}
string strData = Data[Length - 1].ToString(); ;
return strData + Reverse(Data, Length - 1);
}
Bir de en sevdiğim Binary Search Tree nin yüksekliğini hesaplayalım
using System;
namespace IntroSample4
{
class Class3
{
static void Main(string[] args)
{
BinaryTree t = new BinaryTree();
for (int i = 0; i < 20; i++)
{
t.Add(i);
}
t.Show();
Console.WriteLine("The height of the Tree is {0}", t.GetHeight());
}
}
class Node
{
private Node leftNode;
private Node rightNode;
private int data;
public Node(int data)
{
this.data = data;
this.rightNode = null;
this.leftNode = null;
}
public int Data
{
get { return this.data; }
}
public Node LeftNode
{
get { return this.leftNode; }
set { this.leftNode = value; }
}
public Node RightNode
{
get { return this.rightNode; }
set { this.rightNode = value; }
}
}
class BinaryTree
{
private Node root;
public BinaryTree()
{
root = null;
}
public void Add(int x)
{
Node newNode = new Node(x);
//check root
if (root == null)
{
root = newNode;
return;
}
Node temp = root;
while (true)
{
if (newNode.Data > temp.Data)
{
if (temp.RightNode != null)
{
temp = temp.RightNode;
continue;
}
else
{
temp.RightNode = newNode;
return;
}
}
else
{
if (temp.LeftNode != null)
{
temp = temp.LeftNode;
continue;
}
else
{
temp.LeftNode = newNode;
return;
}
}
}
}
private void show(Node n)
{
if (n != null)
{
this.show(n.LeftNode);
this.show(n.RightNode);
Console.WriteLine(n.Data);
}
}
public void Show()
{
this.show(root);
}
private int getHeight(Node n)
{
//int height = 0;
int rHeight = 0;
int lHeight = 0;
if (n.LeftNode != null)
lHeight = 1 + getHeight(n.LeftNode);
if (n.RightNode != null)
rHeight = 1 + getHeight(n.RightNode);
return (rHeight > lHeight) ? rHeight : lHeight;
}
public int GetHeight()
{
if (root == null)
return 0;
else
return this.getHeight(root);
}
}
}
Kodların hepsi bana aittir ama sadece yukarıdaki resimleri bir üniversitenin slaytlarından koydum onu paintte yapamayacağım için flash gibi şeyleri de bilmediğim için hemen bir referans koydum neyse ki.
Referanslar:
http://www.cse.unr.edu/~monica/Courses/CS477-677/Lectures/lecture3.ppt
Introduction to Algorithms Thomas H. Cormen , Charles E.Leiserson, Ronald L. Rivest, Clifford Stein
MIT Press