Muhammet Esat BÜYÜKBULUT

DS 001 – Recursion

—

by

Muhammet Esat BÜYÜKBULUT

in Uncategorized

Kendi kendini çağıran fonksiyonlara recursive fonksiyonlar diyoruz. Bazı problemlerin daha kolay çözülebilmesi için faydalıdır.

Table of Contents

Tipleri

Head recursion: Çağrı fonksiyonun başındaysa
Tail recursion: Çağrı fonksiyonun sonundaysa
Tree recursion: Birden fazla çağrı varsa
Indirect recursion: A->B->A-> farklı fonksiyonlar birbirini ardı ardına çağırıyorsa
Nested recursion: Çağrı içinde parametre olarak başka bir çağrı yapıyorsa

// head recursion
fun(int i){
  if(i>0){
    fun(i-1);
    cout<<i;
  }
}

// tail recursion
fun(int i){
  if(i>0){
    cout<<i;
    fun(i-1);
  }
}

// Tree recursion
fun(int i){
  ...
  return fun(i-1) * fun(i-2);
  ...
}

// Indirect recursion 
a(){
  b();
}

b(){
  a();
}

// Nested recursion
fun(int i){
  ...
  return fun(fun(i+11));
  ...  
}

Örnekler

Fibonacci

#include <iostream> 
using namespace std;

// fibonacci serisisinde her sayı kendinden 
// önceki iki sayının toplamına eşittir
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 -> sayılar
// 0, 1, 2, 3, 4, 5, 6,  7,  8,  9 -> indeksleri


int fibo(int indeks) {
	// öncelikle bitirme koşulunu yazıyoruz
	if (indeks == 0 || indeks == 1)
		return indeks;

	// genel ifadeyi yazıyoruz
	return fibo(indeks - 1) + fibo(indeks - 2);
}


int main(){
	for (int i = 0; i <= 10; i++)
		cout << fibo(i) << ", ";
}

// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,

Power

Bir sayının üstü, kuvveti:

#include <iostream> 
using namespace std;


int power(int sayi, int kuvvet) {
	if (kuvvet == 0) return 1;

	return sayi * power(sayi, kuvvet - 1);
}


int main(){

	for (int i = 0; i < 10; i++)
		cout << power(2,i) << ", ";
	// 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,
}

Alternatif method

#include <iostream> 
using namespace std;

// Eğer üst çift ise sayının karesi alınıp üst yarıya bölünebilir. 
// 2^4 -> (2^2)^2 -> 4^2 
// yani 2*2*2*2 -> 16 yapmak yerine 
// 2*2 -> 4 => 4*4 -> 16 

int power(int sayi, int kuvvet) {
	if (kuvvet == 0) return 1;

	if (kuvvet % 2 == 0) // kuvvet çiftse
		return power(sayi * sayi, kuvvet / 2);
	else // kuvvet tekse
		return sayi * power(sayi, kuvvet - 1);
}


int main(){

	for (int i = 0; i < 10; i++)
		cout << power(2,i) << ", ";
	// 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,
}

Seri

f(x, n) = 1 + \frac{x}{1!}+ \frac{x^2}{2!}+ \frac{x^3}{3!}+\dots +\frac{x^n}{n!}

#include <iostream> 
using namespace std;

double seri(double x, int n) {
	static double x_power;
	static int factorial;

	if (n == 0) {
		x_power = 1;
		factorial = 1;
		return 1;
	}

	return seri(x, n - 1) +
		x * x_power / n*factorial;
}

int main(){
	cout << seri(5, 5);
}

Comments

Leave a Reply Cancel reply