Software Development Exam  >  Software Development Notes  >  DSA in C++  >  Code: Tower of Hanoi using Recursion

Code: Tower of Hanoi using Recursion | DSA in C++ - Software Development PDF Download

Here's a C++ code to solve the Tower of Hanoi problem using recursion:

#include <iostream>

void towerOfHanoi(int n, char source, char auxiliary, char destination) {

    if (n == 1) {

        // Base case: If there is only one disk, move it from source to destination

        std::cout << "Move disk 1 from " << source << " to " << destination << std::endl;

        return;

    }

    // Move n-1 disks from source to auxiliary peg

    towerOfHanoi(n - 1, source, destination, auxiliary);

    // Move the nth disk from source to destination

    std::cout << "Move disk " << n << " from " << source << " to " << destination << std::endl;

    // Move the n-1 disks from auxiliary peg to destination peg

    towerOfHanoi(n - 1, auxiliary, source, destination);

}

int main() {

    int numDisks;

    std::cout << "Enter the number of disks: ";

    std::cin >> numDisks;

    std::cout << "Tower of Hanoi solution:" << std::endl;

    towerOfHanoi(numDisks, 'A', 'B', 'C');

    return 0;

}

Output:

Enter the number of disks: 3

Tower of Hanoi solution:

Move disk 1 from A to C

Move disk 2 from A to B

Move disk 1 from C to B

Move disk 3 from A to C

Move disk 1 from B to A

Move disk 2 from B to C

Move disk 1 from A to C

Explanation:

  • The towerOfHanoi function is a recursive function that solves the Tower of Hanoi problem. It takes four parameters: 'n' (the number of disks), 'source' (the source peg), 'auxiliary' (the auxiliary peg), and 'destination' (the destination peg).
  • The base case is defined when there is only one disk ('n == 1'). In this case, it simply moves the disk from the source peg to the destination peg and prints the move.
  • For the recursive case ('n > 1'), the function follows the following steps:
  • a. Move 'n-1' disks from the source peg to the auxiliary peg using the destination peg as the temporary peg. This is done by making a recursive call to 'towerOfHanoi' with the parameters: 'n-1', source peg, destination peg, and auxiliary peg.
  • b. Move the nth disk from the source peg to the destination peg and print the move.
  • c. Move the 'n-1' disks from the auxiliary peg to the destination peg using the source peg as the temporary peg. This is done by making another recursive call to towerOfHanoi with the parameters: 'n-1', auxiliary peg, source peg, and destination peg.
  • In the 'main' function, the user is prompted to enter the number of disks.
  • The 'towerOfHanoi' function is called with the initial values: number of disks, source peg ('A'), auxiliary peg ('B'), and destination peg ('C').
  • The solution is printed by the function as it performs the necessary moves.

The Tower of Hanoi problem is a classic example of recursion, where a larger problem is broken down into smaller subproblems. The recursive solution follows the concept of divide and conquer, solving the smaller subproblems and combining the solutions to solve the original problem.

The document Code: Tower of Hanoi using Recursion | DSA in C++ - Software Development is a part of the Software Development Course DSA in C++.
All you need of Software Development at this link: Software Development
153 videos|115 docs|24 tests

Top Courses for Software Development

153 videos|115 docs|24 tests
Download as PDF
Explore Courses for Software Development exam

Top Courses for Software Development

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Summary

,

Important questions

,

MCQs

,

Previous Year Questions with Solutions

,

Free

,

pdf

,

Objective type Questions

,

Code: Tower of Hanoi using Recursion | DSA in C++ - Software Development

,

past year papers

,

Viva Questions

,

Code: Tower of Hanoi using Recursion | DSA in C++ - Software Development

,

Semester Notes

,

Exam

,

shortcuts and tricks

,

mock tests for examination

,

ppt

,

video lectures

,

Code: Tower of Hanoi using Recursion | DSA in C++ - Software Development

,

study material

,

Extra Questions

,

Sample Paper

,

practice quizzes

;