Özyineleme, Algoritma Tasarımı ve Analizi

Hüseyin · 2 Kas 2024

Özyinelemenin Temelleri

Özyineleme Tanımı ve Kavramı

Özyineleme, bir fonksiyonun bir problemi çözmek için kendisini doğrudan veya dolaylı olarak çağırdığı bir programlama tekniğidir. Ana fikir, karmaşık bir problemi çözülmesi daha kolay olan daha basit alt problemlere ayırmaktır. Her özyinelemeli çağrı orijinal problemin daha küçük bir örneğini çözer.
Özyinelemeli Fonksiyonun Bileşenleri

Özyinelemeli bir fonksiyonun tipik olarak iki ana bileşeni vardır:

Temel Durum: Bu, özyinelemenin durduğu koşuldur. Temel durum olmadan, fonksiyon kendini sonsuza kadar çağırır ve yığın taşması hatasına yol açar.
Özyinelemeli Durum: Bu, fonksiyonun kendisini daha küçük veya daha basit bir girdi ile çağırdığı kısımdır.

Özyineleme Nasıl Çalışır?

Özyinelemeli bir fonksiyon çağrıldığında, aşağıdaki adımları gerçekleştirir:

Temel durumun karşılanıp karşılanmadığını kontrol eder. Evet ise, sonucu döndürür.
Temel durum karşılanmıyorsa, bazı işlemler gerçekleştirir ve değiştirilmiş argümanlarla fonksiyonun kendisini çağırır.
Her çağrı, bir programdaki etkin alt programlar veya işlevler hakkında bilgi depolayan bir veri yapısı olan çağrı yığınına yeni bir çerçeve ekler.
Temel duruma ulaşıldığında, fonksiyon geri döner ve çağrı yığını her özyinelemeli çağrıyı çözerek çözülmeye başlar.

Basit Örnekler

Faktöriyel Hesaplama Negatif olmayan bir tamsayının ( n ) faktöriyeli, ( n ) 'den küçük veya ona eşit tüm pozitif tamsayıların çarpımıdır. ( n! ) olarak gösterilir.

int factorial(int n) {
if (n == 0) {
return 1; // Base case: 0! = 1
} else {
return n * factorial(n - 1); // Recursive case
}

Örnek:

C++:

#include <iostream>
using namespace std;

int factorial(int n);

int main() {
cout << factorial(5) << endl;  // Output: 120
return 0;
}

Fibonacci Dizisi Fibonacci dizisi, her sayının kendinden önceki iki sayının toplamı olduğu, genellikle 0 ve 1 ile başlayan bir sayı dizisidir.

int fibonacci(int n) {
if (n <= 1) {
return n; // Base case: fibonacci(0) = 0, fibonacci(1) = 1
} else {
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}
}

Örnek:

C++:

#include <iostream>
   using namespace std;

   int fibonacci(int n);

   int main() {
       cout << fibonacci(5) << endl;  // Output: 5
       return 0;
   }

Özyinelemenin Avantajları

Basitlik: Özyinelemeli çözümler genellikle daha zariftir ve anlaşılması daha kolaydır.
Belirli Problemler için Doğal Uyum: Ağaçlar, grafikler ve diğer hiyerarşik yapıları içeren problemler doğal olarak özyineleme için uygundur.

Özyinelemenin Dezavantajları

Performans: Özyinelemeli çözümler, çoklu fonksiyon çağrıları ve yığın kullanımı nedeniyle daha az verimli olabilir.
Bellek Kullanımı: Her özyinelemeli çağrı yığın alanı tüketir, bu da özyineleme derinliği çok büyükse yığın taşmasına neden olabilir.
Hata Ayıklamada Karmaşıklık: Özyinelemeli fonksiyonların hata ayıklaması ve izlenmesi, özellikle karmaşık problemler için daha zor olabilir.

Özyineleme vs Yineleme

Yineleme: Bir koşul karşılanana kadar bir kod bloğunu tekrarlamak için döngüler (for, while) kullanır. Genellikle bellek ve performans açısından daha verimlidir.
Özyineleme: Benzer alt problemlere bölünebilen problemler için daha sezgisel ve uygulaması daha kolaydır.

Özyineleme Ne Zaman Kullanılır?

Problem benzer alt problemlere bölünebildiğinde.
Problem ağaç veya grafik yapıları içerdiğinde.
Yinelemeli çözümün uygulanması çok karmaşık olduğunda.

Özyinelemeli Fonksiyonlar için Örnek

Programlamada özyinelemeli fonksiyonlar, bir problemi çözmek için kendilerini doğrudan veya dolaylı olarak çağıran fonksiyonlardır. Bu teknik, karmaşık problemleri daha basit alt problemlere böler ve temel duruma ulaşılana kadar her bir alt problemi bağımsız olarak ele alır. Özyinelemeli fonksiyonlar, veri yapılarında gezinme, diziler oluşturma ve belirli matematiksel problem türlerini çözme gibi görevlerde çok önemlidir.
Dizinin Artan Olup Olmadığını Kontrol Etme

Bir dizinin kesinlikle artan olup olmadığını kontrol etmek için özyinelemeli bir yaklaşım, dizinin sonuna ulaşılana kadar her bir elemanı bir sonraki ile karşılaştırmayı içerir. İşte C++'da bir uygulama:

C++:

#include <iostream>
using namespace std;

// Recursive function to check if the array is strictly increasing
bool isIncreasing(int arr[], int size, int currentIndex = 0) {
    // Base case: If currentIndex reaches size - 1, the entire array is checked
    if (currentIndex == size - 1) {
        return true;
    }

    // Recursive call: Check if current element is less than the next element
    if (arr[currentIndex] < arr[currentIndex + 1]) {
        return isIncreasing(arr, size, currentIndex + 1);
    } else {
        return false;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};      // Example increasing array
    int size = sizeof(arr) / sizeof(arr[0]);

    if (isIncreasing(arr, size)) {
        cout << "The array is strictly increasing." << endl;
    } else {
        cout << "The array is not strictly increasing." << endl;
    }

    return 0;
}

Dizinin Azalıp Azalmadığını Kontrol Edin

Benzer şekilde, özyineleme kullanarak bir dizinin kesin olarak azalıp azalmadığını kontrol etmek için, dizinin başlangıcına ulaşılana kadar her elemanı bir sonrakiyle ters sırada karşılaştırırsınız:

C++:

#include <iostream>
using namespace std;

// Recursive function to check if the array is strictly decreasing
bool isDecreasing(int arr[], int size, int currentIndex = 0) {
    // Base case: If currentIndex reaches size - 1, the entire array is checked
    if (currentIndex == size - 1) {
        return true;
    }

    // Recursive call: Check if current element is greater than the next element
    if (arr[currentIndex] > arr[currentIndex + 1]) {
        return isDecreasing(arr, size, currentIndex + 1);
    } else {
        return false;
    }
}

int main() {
    int arr[] = {5, 4, 3, 2, 1};      // Example decreasing array
    int size = sizeof(arr) / sizeof(arr[0]);

    if (isDecreasing(arr, size)) {
        cout << "The array is strictly decreasing." << endl;
    } else {
        cout << "The array is not strictly decreasing." << endl;
    }

    return 0;
}

Bir Dizideki Elemanın İlk Oluşumunu Bulma

Bir dizideki bir elemanın ilk oluşumunu bulmak için özyinelemeli bir yaklaşım, eleman bulunana veya dizinin sonuna ulaşılana kadar her elemanın hedef elemanla karşılaştırılmasını içerir. İşte C++'da bir uygulama:

C++:

#include <iostream>
using namespace std;

// Recursive function to find the first occurrence of a target in an array
int findFirstOccurrence(int arr[], int size, int target, int currentIndex = 0) {
    // Base case: If currentIndex reaches size, return -1 (target not found)
    if (currentIndex == size) {
        return -1;
    }

    // Check if current element equals target
    if (arr[currentIndex] == target) {
        return currentIndex;
    }

    // Recursive call to check the rest of the array
    return findFirstOccurrence(arr, size, target, currentIndex + 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 2, 5, 2};  // Example array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 2;

    int firstIndex = findFirstOccurrence(arr, size, target);

    if (firstIndex != -1) {
        cout << "The first occurrence of " << target << " is at index " << firstIndex << endl;
    } else {
        cout << target << " is not found in the array" << endl;
    }

    return 0;
}

Bir Dizideki Bir Öğenin Son Oluşumunu Bulma

Bir dizideki bir öğenin son oluşumunu bulmak için özyinelemeli bir yaklaşım, öğe bulunana veya dizinin başlangıcına ulaşılana kadar, son öğeden başlayarak ve ilk öğeye doğru ilerleyerek her öğeyi hedef öğeyle karşılaştırmayı içerir. İşte C++'da bir uygulama:

C++:

#include <iostream>
using namespace std;

// Recursive function to find the last occurrence of a target in an array
int findLastOccurrence(int arr[], int size, int target, int currentIndex = 0) {
    // Base case: If currentIndex reaches -1, return -1 (target not found)
    if (currentIndex == -1) {
        return -1;
    }

    // Check if current element equals target
    if (arr[currentIndex] == target) {
        return currentIndex;
    }

    // Recursive call to check the previous element
    return findLastOccurrence(arr, size, target, currentIndex - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 2, 5, 2};  // Example array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 2;

    int lastIndex = findLastOccurrence(arr, size, target, size - 1);

    if (lastIndex != -1) {
        cout << "The last occurrence of " << target << " is at index " << lastIndex << endl;
    } else {
        cout << target << " is not found in the array" << endl;
    }

    return 0;
}

Bir Dizideki Bir Öğenin Tüm Oluşumlarını Yazdırma

Bir dizideki bir öğenin tüm oluşumlarını yazdırmak için özyinelemeli bir yaklaşım, her öğeyi hedef öğeyle karşılaştırmayı ve öğe bulunduğunda dizini yazdırmayı içerir. Fonksiyon, tüm elemanlar yazdırılana kadar dizi içinde özyinelemeli olarak arama yapmaya devam eder. İşte C++'da bir uygulama:

C++:

#include <iostream>
using namespace std;

// Recursive function to print all occurrences of a target in an array
void printAllOccurrences(int arr[], int size, int target, int currentIndex = 0) {
    // Base case: If currentIndex reaches size, return (end of array)
    if (currentIndex == size) {
        return;
    }

    // Check if current element equals target
    if (arr[currentIndex] == target) {
        cout << "Found at index " << currentIndex << endl;
    }

    // Recursive call to check the next element
    printAllOccurrences(arr, size, target, currentIndex + 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 2, 5, 2};  // Example array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 2;

    cout << "Occurrences of " << target << " in the array:" << endl;
    printAllOccurrences(arr, size, target);

    return 0;
}

Özyineleme Kullanarak Dizeyi Sayıya Dönüştürme

C++'da özyineleme kullanarak bir sayının dize gösterimini tamsayıya dönüştürmek, dizenin her karakterini özyinelemeli olarak işlemeyi, sayısal değerine dönüştürmeyi ve sonucu toplamayı içerir. Dizenin son karakterinden başlayarak bunu nasıl uygulayabileceğiniz aşağıda açıklanmıştır:

C++:

#include <iostream>
#include <string>
using namespace std;

// Helper function to calculate the integer value of a character (digit)
int charToInt(char c) {
    return c - '0';
}

// Recursive function to convert string to integer starting from the last character
int stringToNumber(const string& str, int index) {
    // Base case: If index goes below 0, return 0
    if (index < 0) {
        return 0;
    }

    // Recursive call to process the previous character and multiply by 10
    int num = stringToNumber(str, index - 1);
    int digit = charToInt(str[index]);



    return num * 10 + digit;
}

int main() {
    string str = "12345"; // Example string representing a number
    int lastIndex = str.size() - 1;
    int number = stringToNumber(str, lastIndex);

    cout << "String \"" << str << "\" converted to number: " << number << endl;

    return 0;
}

Özyineleme Kullanarak Dizeyi Ters Sayıya Dönüştürme

C++'da özyineleme kullanarak bir sayının dize gösterimini ters tamsayı biçimine dönüştürmek için, dizenin her karakterini özyinelemeli olarak işleyebilir ve sayıyı ters sırada toplayabilirsiniz. Bunu şu şekilde uygulayabilirsiniz:

C++:

#include <iostream>
#include <string>
using namespace std;

// Recursive function to convert string to reverse number
int stringToReverseNumber(const string& str, int index = 0) {
    // Base case: If index reaches the end of the string, return 0
    if (index == str.size()) {
        return 0;
    }

    // Recursive call to process the next character and multiply by 10
    int num = stringToReverseNumber(str, index + 1);
    int digit = str[index] - '0';

    return num * 10 + digit;
}

int main() {
    string str = "12345"; // Example string representing a number
    int reversedNumber = stringToReverseNumber(str);

    cout << "String \"" << str << "\" converted to reverse number: " << reversedNumber << endl;

    return 0;
}

4xN Grid için Döşeme Problemi

Problem, 4xN'lik bir ızgarayı 4x1 karolar veya 1x4 karolar kullanarak döşemeyi içermektedir. Bu karoları kullanarak ızgarayı tamamen kaplamanın kaç yolu olduğunu belirlememiz gerekiyor.

C++:

#include <iostream>
using namespace std;

// Recursive function to count the number of ways to tile a 4xN grid
int countWaysToTile(int n) {
    // Base cases
    if (n <= 0) {
        return 0;
    }
    if (n == 1 || n == 2 || n == 3) {
        return 1; // Only one way to tile for these cases using 4x1 tiles
    }
    if (n == 4) {
        return 2; // Two ways to tile a 4x4 grid (either four 1x4 tiles or sixteen 1x1 tiles)
    }

    // Recursive calls considering placing either a vertical 4x1 tile or a horizontal 1x4 tile
    return countWaysToTile(n - 1) + countWaysToTile(n - 4);
}

int main() {
    int n = 5; // Example grid size (4x5)
    int ways = countWaysToTile(n);

    cout << "Number of ways to tile a 4x" << n << " grid: " << ways << endl;

    return 0;
}

1, 2 ve 3 Basamaklı Merdiven Çıkma Sorunu

Merdiven çıkma problemi, n basamaklı bir merdivenin tepesine ulaşmanın farklı yollarının sayısını belirlemeyi içerir. Her seferinde 1, 2 veya 3 adım atabilirsiniz. İşte bu problemi C++'da çözmek için özyinelemeli bir yaklaşım:

C++:

#include <iostream>
using namespace std;

// Recursive function to count the number of ways to climb stairs with 1, 2, or 3 steps
int climbStairs(int n) {
    // Base cases
    if (n == 0) {
        return 1; // Base case: One way to stay at ground level
    }
    if (n < 0) {
        return 0; // Base case: No ways to go below ground level
    }
    if (n == 1) {
        return 1; // Only one way to climb 1 step (take one 1-step)
    }

    // Recursive calls considering taking either 1, 2, or 3 steps
    return climbStairs(n - 1) + climbStairs(n - 2) + climbStairs(n - 3);
}

int main() {
    int n = 4; // Example number of steps
    int ways = climbStairs(n);

    cout << "Number of ways to climb " << n << " steps: " << ways << endl;

    return 0;
}

Ardışık 1'ler Olmayan İkili Dizeler Oluşturma

C++'da özyineleme kullanarak ardışık 1'ler olmadan n uzunluğunda ikili dizeler üretme problemini çözmek için aşağıdaki yaklaşımı uygulayabiliriz:

C++:

#include <iostream>
using namespace std;

// Recursive function to count binary strings of length n with no consecutive 1s
int countBinaryStrings(int n, bool lastWasOne = false) {
    // Base case: If length is 0, return 1 (empty string)
    if (n == 0) {
        return 1;
    }

    // Initialize count
    int count = 0;

    // If last character was '1', current character can only be '0'
    if (lastWasOne) {
        count += countBinaryStrings(n - 1, false);
    }
    // If last character was '0', current character can be either '0' or '1'
    else {
        count += countBinaryStrings(n - 1, false); // Try appending '0'
        count += countBinaryStrings(n - 1, true);  // Try appending '1'
    }

    return count;
}

int main() {
    int n = 4; // Example length of binary strings
    int ways = countBinaryStrings(n);

    cout << "Number of binary strings of length " << n << " with no consecutive 1s: " << ways << endl;

    return 0;
}

Özyineleme Kullanarak Bir Dizenin Tüm Alt Kümelerini/Alt Dizilerini Oluşturma

Özyineleme kullanarak belirli bir dizenin tüm alt kümelerini (alt dizilerini) oluşturmak için, dizenin her karakterini içeren veya hariç tutan özyinelemeli bir işlev uygulayabilirsiniz. İşte bunu C++'da nasıl yapabileceğiniz:

C++:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Recursive function to generate all subsets/subsequences of a given string
void generateSubsets(const string& str, string current, int index, vector<string>& result) {
    // Base case: If index reaches the length of the string, add the current subset to the result
    if (index == str.size()) {
        result.push_back(current);
        return;
    }

    // Exclude the current character and recurse
    generateSubsets(str, current, index + 1, result);

    // Include the current character and recurse
    generateSubsets(str, current + str[index], index + 1, result);
}

int main() {
    string str = "abc"; // Example string
    vector<string> subsets;

    // Generate all subsets
    generateSubsets(str, "", 0, subsets);

    // Print all generated subsets
    cout << "All subsets of \"" << str << "\":" << endl;
    for (const string& subset : subsets) {
        cout << "\"" << subset << "\"" << endl;
    }

    return 0;
}

Özyineleme, Algoritma Tasarımı ve Analizi

Daha fazla seçenek

Hüseyin

Üye