Join Raghavendra Dixit for an in-depth discussion in this video Introduction, part of Introduction to Data Structures & Algorithms in Java.
- [Instructor] In this chapter, we will learn what recursion is. We will start by implementing the factorial method using recursion. Then we will see how the recursion call stack works. Then we will move on to implementing a couple of more algorithms using recursion, the Tower of Hanoi and the merge sort, all right? So let us start off by revisiting Euclid's algorithm, something which you have already seen earlier. Now this is a recursive algorithm because the gcd method or function calls itself until it evaluates to some integer value, which is returned, and the integer value is evaluated when the parameter b passed to the gcd method is zero, and this is called the breaking condition, and it is very important to have a breaking condition in recursive method calls.
Until b is zero, the gcd method will keep calling itself over and over, okay? So recursion is when a method calls itself from within the same method. Now, let's look at how we calculate the factorial of a method. So factorial of n is n into n minus one into n minus two all the way up to one, right? So we can initialize a variable with a value of one, and then in a for loop, we keep multiplying integers from one to n to the result, and storing it back in the same variable.
And finally, when we are done, we return the result, all right? So this way of calculating factorial is an iterative way, because we iterate through all the numbers from one to n. But again, the factorial of a number n is defined as this, and it can also be written as n into factorial of n minus one. We have just grouped a part from n minus one onwards, all right? So if we implement factorial recursively, we can write the factorial method like this.
Now, let's implement the factorial method in Java, and run it to see if it works. As you can see, we get a stack overflow exception. So what went wrong? Well, we forgot to put the breaking condition, because of which, the factorial kept calling itself over and over, unless it ran kind of out of memory, and we will understand why that happens, but the important point is that you must put a breaking condition.
Otherwise, you will get a runtime error. So we'll put the breaking condition, or the base condition as if n is zero, we return one, because factorial of zero is one, and factorial of negative numbers is not defined, so if you want to put another check, that is, if n is less than zero, we put another exception saying that factorial for that n is undefined. Anyways, so if we run the program again, after putting the base condition, we get the correct value of the factorial of this number.
So while using recursion in a program, make sure that you always put a correct breaking or base condition. Now, if you compare this recursive program to the iterative one, you can see that the recursive way is much more concise and cleaner, so recursion has its pros and cons. The recursive way makes our problems very concise and easy to understand, but the iterative way performs better in terms of how fast it runs or how much memory is consumed.
Also, recursion may cause stack overflow errors in case the depth of recursion is not small. But suppose you have the right program to solve the Rubik's cube, or to solve the Tower of Hanoi. This kind of programs are very difficult to implement iteratively, but then, recursion requires a little getting used to. So if you are new to this, I advise that you try out all the problems in the chapter exercise and think about simple algorithms, which may also be done recursively.
Note: This course was created by Packt Publishing. We are pleased to host this training in our library.
- Why study data structures and algorithms?
- How to calculate the time complexity
- Using Big O notation
- Using basic sorting and search algorithms
- Searching elements in unordered arrays and ordered arrays
- Implementing a linked list in Java
- Implementing stacks using arrays
- Queues using arrays
- Binary search trees
- Representing heaps using arrays
Skill Level Intermediate
1. Introduction to Algorithms
2. Analysis of Algorithms
3. Basic Sorting and Search Algorithms
4. Linked Lists
5. Stacks and Queues
7. Binary Search Trees
8. More Sorting Algorithms
- Mark as unwatched
- Mark all as unwatched
Are you sure you want to mark all the videos in this course as unwatched?
This will not affect your course history, your reports, or your certificates of completion for this course.Cancel
Take notes with your new membership!
Type in the entry box, then click Enter to save your note.
1:30Press on any video thumbnail to jump immediately to the timecode shown.
Notes are saved with you account but can also be exported as plain text, MS Word, PDF, Google Doc, or Evernote.