We will look at stack and few things about recursion and then some problems to be practiced.
Overview
To be honest, recursion is the most important topic over all others. You will be using it for binary search, heap, graphs, reversals, dynamic programming and so on.
What is Call Stack ?
It is a stack that tracks the program executions, also known as execution stack, program stack, control stack, run-time stack, or machine stack.
As we call the functions, the call stack arranged the function executions itself and work according to LIFO nature.
Note: Once the function done their job, it get removed from the call stack.
How good you are at imagining the call stack is going to give you more control on recursion.
Recursion
Recursion does not take constant space, because the call stack takes the memory spaces. Which will be O(n) in linear recurrence.
The recursive solutions look simple but visualization and tracing takes time and space.
A recurrence is an equation or inequality that describes a function in terms of its values on smaller inputs.
There are two types of recurrence, linear recurrence and divide and conquer recurrence. The divide and conquer is better than the linear recurrence, because it halfs the area of input to work on, on each recursive calls.
Linear recurrence : Fibonacci series
Divide and conquer recurrence : Binary Search
While writing recursive functions, make sure to be right at choosing what to be in argument and what should be in functions body.
Solving problems on recursion
Write the below programs using recursion to get a good control on it.
- Sum of digits with recursion
- Product of digits with recursion
- Reverse a string
- Count zero in number using recursion
- Linear search with recursion
- Binary search with recursion
- Check if array is sorted with recursion
