what is recursion?
what is recursion?
what is recursion?
what is recursion?
Before learning Recursion you must have knowledge about function, parameters, and its return type. They are very easy to learn, just google or search on youtube about "function".
Recursion is a method when a function calls itself and works with some other inputs. Every recursion function has almost the same following components.
void f(// State ){
// Base or terminating case
// Operations on state, and possible calls to f() function again
}
The state is nothing but the parameters of a function.
Recursion is a kind of infinite loop, not like that but you can imagine - every time the function call by itself so after some operations, you must have to stop the process, this is called base case or terminating case.
Recursion is a kind of infinite loop, not like that but you can imagine - every time the function call by itself so after some operations, you must have to stop the process, this is called base case or terminating case.
For better understanding let's illustrate, calculating the sum of an array obviously using recursion.
Look at the picture carefully I have tried to illustrate the internal view of recursion, what happened when we call a recursion function, it actually creates another recursion function and stores all of them in a Stack. After reaching the base case it stops storing function in stack, and we know stack work with a property that is LIFO(Last-In-First-Out), so the last calling function will operate first. We see here the 5th function that returns 0 after that will be removed from the stack after another function will be called and so on. Initially, the main function was already stored in the stack, that's why after processing all other functions, the main function operates in the last.
So, now we know what is recursion and how it works. If we try to sum up what we need to do when we solve recursive related problems that are,
So, now we know what is recursion and how it works. If we try to sum up what we need to do when we solve recursive related problems that are,
1. What is the state?
2. What is the best case?
2. What is the best case?
3. And finally what do we want to achieve?
Backtracking:
Backtracking is similar to recursion. It is actually a general method of trying all possible solutions to a problem using recursively.
We can't solve all problems using backtracking, because generating a number of possible solutions can be huge, so it is only applicable if and only if the number of inputs is small and at the same time there is no other better algotithm.
For better understanding, we need to solve problems using backtracking. Near future, I will discuss some problems. For now try some problems given below.
Related problems,
Climbing Stairs - Easy
Climbing Stairs - Easy
No comments:
Post a Comment