recursive_algorithms_cpp.cpp

# -*- coding: utf-8 -*-
"""Recursive_Algorithms.cpp

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/1hQMv6ceS8Py0qpN2W7I3s1g07IAqh1SX
"""

# Commented out IPython magic to ensure Python compatibility.
# %%writefile tower_of_hanoi.cpp
# #include <iostream>
# using namespace std;
# 
# void towerOfHanoi(int n, char source, char destination, char buffer) {
#     if (n == 1) {
#         cout << "Move package 1 from " << source << " to " << destination << endl;
#         return;
#     }
#     // Move n-1 packages from source to buffer
#     towerOfHanoi(n - 1, source, buffer, destination);
#     // Move the nth package to destination
#     cout << "Move package " << n << " from " << source << " to " << destination << endl;
#     // Move n-1 packages from buffer to destination
#     towerOfHanoi(n - 1, buffer, destination, source);
# }
# 
# int main() {
#     int n; // Number of packages
#     cout << "Enter the number of packages: ";
#     cin >> n;
#     // Call Tower of Hanoi for n packages
#     towerOfHanoi(n, 'A', 'C', 'B'); // A is source, C is destination, B is buffer
#     return 0;
# }
#

!g++ -o hanoi tower_of_hanoi.cpp

!./hanoi

"""#**The Recursive Process**

When I use recursion to solve the Tower of Hanoi, I’m essentially breaking the problem down into smaller, manageable parts. Here’s how it works step-by-step:


> 1. Base Case: The simplest scenario occurs when there is only one disc to move. In this case, I just move that single disc from the source rod to the destination rod. This step doesn’t require any further recursion.

> 2. Recursive Case: If I have more than one disc (let’s say n discs):
> *  First, I need to move the top n−1 discs from the source rod to the buffer rod.
> *  Next, I move the largest disc (the n^th disc) directly from the source rod to the destination rod. This is a single move and doesn’t require recursion.
> *  Finally, I move the n−1 discs from the buffer rod to the destination rod. Again, this step requires another recursive call.




So, the recursive function will keep calling itself until it reaches the base case, where it can directly move a single disc. Each recursive call effectively reduces the problem size by one disc until I reach that point.


**Recursive Function Breakdown**

To summarize the recursive steps:



*   Move n−1 discs from source to buffer (recursive call).
*   Move the n^th disc from source to destination.
*   Move n−1 discs from buffer to destination (recursive call).




# **Time Complexity Analysis**

Now, let’s analyze the time complexity:

*   If T(n) represents the number of moves required to solve the problem for n discs, the recursive relationship can be defined as:

`T(N) = 2 8T(n - 1) + 1`


*   This is because I need to solve the problem for n−1 discs twice (once to move to the buffer and once to move to the destination) and then make one move for the largest disc.

*   If I keep expanding this relationship, I find that the total number of moves is:

`T(n) = 2^n - 1`

*   Time Complexity: Therefore, the time complexity is O(2^n), which is exponential. This means that as the number of discs increases, the number of moves required grows very quickly, making it increasingly time-consuming to solve for larger values of n.



**Conclusion**

In essence, recursion helps me break down the Tower of Hanoi problem into simpler subproblems, allowing me to solve each part step-by-step. However, the exponential time complexity highlights that while the recursive approach is elegant and straightforward, it can become impractical for a large number of discs due to the rapid increase in the number of moves required.
"""