Rekursion()

[ALcatraz']

Rekursion()

Rekursion'un sonsuzluk ile bir ilişkisi var. Ben biliyorum ki rekursion'un sonsuzluk ile bir ilişkisi var.
Ihan3t rekursion'un sonsuzluk ile bir ilişkisi olduğunu bildiğimi düşünüyor. Osman %100 biliyor ihan3tin, rekursion'un sonsuzluk ile bir ilişkisi olduğunu ve bunu bildiğimi düşündüğünü. Ama biz inanmıyoruz Osmanın %100 bildiğine, ihan3tin düşündüğüne ve benim rekursion'un sonsuzluk ile bir ilişkisi olduğunu bildiğime.

Mesela bu konuşma oyununu örnek olarak alabiliriz. Bu örnek Rekursion sanatının doğal anlatımı. Bizim bütün düşüncelerimiz, rekursion ile bağdaşıyor.

Rekursion kelimesi latinceden "recurrere" den geliyor ve anlamı "Geri gitmek, geri koşmak". Aslında bu kelimenin anlamı Rekursion fonksiyonlarının ne yaptığını anlamaniza yetiyordur umarım. Evet şimdi olayları elimize alalım, olayın matematik tarafı anlaması kolay ve sizin rekursion programlamanızı kolaylaştırır. Evet bizde fakültede ki geleneklere uyup bu yazımda fonksiyonumuzu geleneklere göre anlatalım.

Matematiksel olarak böyle tanımlanmıştır;

n! = n * (n-1)!, if n > 1 and f(1) = 1

Sonlandırma Kriteri

Extra kırmızı yazdım önemli olduğu için. Eğer rekursion'u kullanmak istiyorsanız bir sonlandırma kriteri belirtmek zorundasınız aksi halde sonsuz bir döngüye sokabilirsiniz. Mesela bir if içinde sonlandırma koşulu sağlanana kadar bir değişken içinde saydırabilirsiniz.

Fakülteden bir örnek;

4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1

4! için;

4! = 4 * 3 * 2 * 1

Rekursion Python

Evet bir örnek seçelim fazla uzağa gitmeden biraz önce ("bana göre 4 saat") faktöriyel konusunu ele alalım. Python kodlarınında matematik gibi elegant-kibar olduğunu göreceksiniz

def fakt(n): 
*** if n == 1:
******* return 1 
*** else:
******* return n * fakt(n-1)

Evet buyrun ama derseniz ki ben bunun çalışma mantığını anlamadım o zaman 2 print ile hemen daha kolay anlayabilmenizi sağlayabiliriz;

def fakt(n): 
*** print("faktoriyel cagrildi* n = " + str(n)) 
*** if n == 1: 
******* return 1
*** else: 
******* res = n * fakt(n-1) 
******* print("sonucumuz ", n, " * fakt(" ,n-1, "): ",res)********* 
******* return res
***** 	 print(fakt(5))

Python scriptimizden gelecek sonuç;

faktoriyel cagrildi n = 5 
faktoriyel cagrildi n = 4 
faktoriyel cagrildi n = 3 
faktoriyel cagrildi n = 2 
faktoriyel cagrildi n = 1 
sonucumuz 2 * fakt( 1 ): 2 
sonucumuz 3 * fakt( 2 ): 6 
sonucumuz 4 * fakt( 3 ): 24
sonucumuz 5 * fakt( 4 ): 120 
120

iterative bir fonksiyonda yazabiliriz;

def iterative_fakt(n): 
*** sonuc = 1 
*** for i in range(2,n+1): 
******* sonuc *= i 
*** return sonuc

Aslında bu konuya verilebilecek en iyi örneklerden biri fibonacci serisidir ama onu yazmakla uğraşamayacağım gibi ("mobilden yazdığım için") direk ihan3t'imin sizlere konusunu atayım aslında orda da tam olarak bu konuya ve dinamik programlamaya değinmeye çalıştı bende az şu kadar bilgim ile bir makale yazdım, sağlıcakla kalın.

Mobilde olduğum için kodlarda ve yazılarda yanlış olabilir, affedin Bu arada Rekursion;
İngilizce: Recursion
Türkçe: Özyineleme

Vee konuyu bulamadığım için devam yazmaya

Şimdi zamanım olmadığından wikiden fibonacciyi kopyalıcam.

/* Fibonacci dizisi, her sayının kendinden öncekiyle toplanması sonucu oluşan bir sayı dizisidir. Bu şekilde devam eden bu dizide sayılar birbirleriyle oranlandığında altın oran ortaya çıkar, yani bir sayı kendisinden önceki sayıya bölündüğünde*altın orana*gittikçe yaklaşan bir dizi elde edilir. Bu durumda genel olarak n'inci*Fibonacci*sayısı F şu şekilde ifade edilir. */

Kolay bir fibonacci scripti şu sekilde yapılabilir;

a,b=0,1
while b<100:
    print (b)
    a,b=b,a+b

Birde rekursion işlemiyle bakalım;

def fib(n): 
    if n == 0: 
        return 0 
   elif n == 1: 
       return 1 
   else: 
       return fib(n-1) + fib(n-2)

Bide bunu iterative bir biçimde değistirelim;

def fibi(n): 
    eski, yeni = 0, 1 
    if n == 0: 
        return 0 
    for i in range(n-1): 
        eski, yeni = yeni, eski + yeni 
        return yeni

Bu kadaaaarrr.
Hayırlı forumlar tekrardan hatalarım var ise affola.
​

 

[nS4f3]

Hocam harika anlatım olmuş.
Bildiğim halde öğrendim :

 

[hectovecto]

İşte hoca sen anlattın da dinlemedik mi :trl

 

[ihan3t]

Ellerine sağlık dostum, ithafların için ayrıca teşekkürler.

Algoritma yarışması 2 adlı konumu bende bulamadım, birisi sebepsiz yere kaldırmış. Sanırım foruma faydalı konu açma yasağı geldi haberim yok.


Onun için fibonnacci serisinde dynamic programming tekniği olan memoization kodunu da ben yazayım :

import profile
import sys
sys.setrecursionlimit(100000)

def mfib(n):
    cache = [-1 for x in range(n+1)]
    cache[0] = 0
    cache[1] = 1

    return fib(n, cache)

def fib(n, cache):
    if cache[n] != -1:
        return cache[n]
    else:
        cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
        return cache[n]

profile.run('print mfib(20)')

Burada maksat bir kere çalıştırılan adımın hafızaya alınıp tekrar o adıma başka bir node dan gelindiğinde hali hazırda hesaplanmış sonucun dönülmesi, böylece adım sayısını decrease etmek.

 

[ALcatraz']

Tesekkurler elimizden geldiği kadar anlatmaya devam.

Ellerine sağlık dostum, ithafların için ayrıca teşekkürler.

Algoritma yarışması 2 adlı konumu bende bulamadım, birisi sebepsiz yere kaldırmış. Sanırım foruma faydalı konu açma yasağı geldi haberim yok.


Onun için fibonnacci serisinde dynamic programming tekniği olan memoization kodunu da ben yazayım :

import profile
import sys
sys.setrecursionlimit(100000)

def mfib(n):
    cache = [-1 for x in range(n+1)]
    cache[0] = 0
    cache[1] = 1

    return fib(n, cache)

def fib(n, cache):
    if cache[n] != -1:
        return cache[n]
    else:
        cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
        return cache[n]

profile.run('print mfib(20)')

Burada maksat bir kere çalıştırılan adımın hafızaya alınıp tekrar o adıma başka bir node dan gelindiğinde hali hazırda hesaplanmış sonucun dönülmesi, böylece adım sayısını decrease etmek.

Seninde ellerine sağlik tekrardan yordun ellerini benim için dostum Konunu yarım saat aramama değmedi demek ki, kendileri anlayamadığı için kaldırıyodurlar

 

[b0mb]

Ellerine sağlık abi, güzel bir yazı olmuş

 

[ALcatraz']

Ellerine sağlık abi, güzel bir yazı olmuş

O senin güzelliğin kardeşim

 

[kenzai]

eline sağlık

 

[Phoique 7]

Elinize sağlık, geçen gün bu konuyu araştırıyordum. Buda üstüne denk gelince çok iyi oldu sağolun.

 

[ALcatraz']

Elinize sağlık, geçen gün bu konuyu araştırıyordum. Buda üstüne denk gelince çok iyi oldu sağolun.

Önemli değil

 

[ihan3t]

Hem konuya update geçmiş olayım hemde bu sırada geri getirilen konumun linkini buraya vereyim : http://www.turkhackteam.org/yarisma...lgoritma-optimizasyon-yarismasi-2-ihan3t.html

 

[lTURK]

Teşekkürler baya güzel anlatım olmuş ileri düzeyde anlatımlar bekliyorum