# Tail-Recursion-Programs
[Programs (Tail-Recursive)](https://github.com/Akshaya-Amar/Tail-Recursion-Programs#programs)
**Non-tail recursion to Tail recursion** will lead from slower execution **to faster execution and** from O(n) space **to O(1) space**
**Recursion is slow** because of the **time spend in pushing and popping the activation records** on and from the stack for each recursive call and **expensive in terms of memory** as well because **it requires space in the stack to store the activation records** for each recursive call and **if the stack is too deep, then stack may overflow.**
This can be improved by making recursive program as **tail recursive** as **it doesn't involves pushing and popping operations**, rather the previous activation record gets overwrittern by the current activation record when a recursive call occurs, while retaining the original return address. So, at a time we have only one activation record on the stack and that too for the currently executing recursive call. So, it doesn't matter that how deep the recursion is, **the space requirement will always be constant** and **improves the overall performance by reducing the time and space/memory requirements.**
Non-tail recursion
A recursive call is said to be non-tail recursive if it is not the last statement to be executed inside a function or that call is a part of expression.
eg:
```
int fact(int num) {
if(num == 1) {
return 1;
}
return num * fact(num - 1); // not a tail recursive call as it is a part of expression
}
```
To find factorial of 5 using non-tail recursion
**fact(5)**
**5 * fact(4)**
**5 * (4 * fact(3))**
**5 * (4 * (3 * fact(2)))**
**5 * (4 * (3 * (2 * fact(1))))**
**5 * (4 * (3 * (2 * 1)))**
**5 * (4 * (3 * 2))**
**5 * (4 * 6)**
**5 * 24**
**120**
Non-Tail recursive functions have to finish the pending work after the recursive call finishes, so activation record for each recursive call has to be maintained in the stack. Here, after the recursive call, we still need to remember to multiply later on, in order to get the desired results, and to remember, space is required in order to store the activation record in the stack for each recursive call which will degrade performance and will not be space efficient.
Tail recursion
A recursive call is said to be tail recursive if it is the last statement to be executed inside a function and that call is not a part of expression.
eg:
```
int fact(int num, int res){
if(num == 1){
return res;
}
return fact(num - 1, num * res); // tail recursive call
}
```
**A recursive function can be converted into a tail recursive function using an auxiliary parameter**(like we have used (res) in our case). The result is accumulated in this parameter and this is done in such a way that there is no pending operation left after the recursive call.
To find factorial of 5 using tail recursion
**fact(5, 1)**
**fact(4, 5)**
**fact(3, 20)**
**fact(2, 60)**
**fact(1, 120)**
**120**
In tail recursive function, since no pending operations are left after making a recursive call so, no need to store the record of the previous state i.e. no need to push a new activation record for each recursive call in the stack. Here, we are performaing running multiplication using the auxiliary variable(res) on the fly as we move along instead of waiting till the end and doing multiplication backwards. So, nothing to remember and therefore no need to store activiation record for each recursive call which results in faster performance and will be space efficient as well.
**Tail recursion is a compile level optimisation**. Some modern compiler can detect tail recursion and perform the optimisation by converting it to iteration to improve performance.
**Java, python don't support tail recursion optimisation while C and C++ do.**
Let's try in Java program whether it's supported or not.
```
class Sample {
public static void main(String[] args) {
System.out.println(new Sample().fact(5, 1));
}
private int fact(int num, int res) {
if(num == 1) {
System.out.println(10 / 0);
return res;
}
return fact(num - 1, res * num);
}
}
```
```
Exception in thread "main" java.lang.ArithmeticException: / by zero
at Sample.fact(Sample.java:8)
at Sample.fact(Sample.java:12)
at Sample.fact(Sample.java:12)
at Sample.fact(Sample.java:12)
at Sample.fact(Sample.java:12)
at Sample.main(Sample.java:3)
```
Here, I tried to throw an exception in a tail recursive function and **we can see all the recursive calls in the stack trace** and it can clearly be seen that Java doesn't support tail recursion optimization and **according to Brian Goetz(Java Language Architect @ Oracle) there are number of security sensitive methods in JDK which rely on counting stack frames between JDK library code and calling code to figue out who's calling them.**
**References:**
Data Structures through C in Depth by S.K.Srivastava/Deepali Srivastava,
https://stackoverflow.com/questions/33923/what-is-tail-recursion,
https://softwareengineering.stackexchange.com/questions/272061/why-doesnt-java-have-optimization-for-tail-recursion-at-all
## Programs
| # | Title | Complexity |
|:---:| ----- | :--------: |
|1.|[Factorial Of Number](./FactorialOfNumber.c) | Time - **O(n)**
Space - **O(1)** |
|2.|[Number of Digits In a Number](./NumberOfDigitsInANumber.c) | Time - **O(log10(n))**
Space - **O(1)** |
|3.|[Number Of Even Elements In Array](./NumberOfEvenElementsInArray.c) | Time - **O(n)**
Space - **O(1)** |
|4.|[Reverse Integer](./ReverseInteger.c) | Time - **O(log10(n))**
Space - **O(1)** |
|5.|[Sum Of Digits](./SumOfDigits.c) | Time - **O(log10(n))**
Space - **O(1)** |
|6.|[Sum Of Elements In Array](./SumOfElementsInArray.c) | Time - **O(n)**
Space - **O(1)** |
|7.|[Binary Search](./BinarySearch.c) | Time - **O(log2(n))**
Space - **O(1)** |
|8.|[Pow(x, n)](./FindPower.c) | Time - **O(log2(n))**
Space - **O(1)** |
|9.|[Minimum Element In Array](./MinElementInArray.c) | Time - **O(n)**
Space - **O(1)** |
|10.|[Perfect Number](./PerfectNumber.c) | Time - **O(n)**
Space - **O(1)** |
|11.|[Sum Of First N Natural Numbers](./SumOfFirstNNaturalNumbers.c) | Time - **O(n)**
Space - **O(1)** |
|12.|[Number Of Times Digits Encountered](./NumberOfTimesDigitsEncountered.c) | Time - **O(log10(n))**
Space - **O(1)** |
|13.|[Palindrome Number](./PalindromeNumber.c) | Time - **O(log10(n))**
Space - **O(1)** |
|14.|[Sum Of Proper Divisor](./SumOfProperDivisor.c) | Time - **O(n)**
Space - **O(1)** |
|15.|[Greatest Common Divisor(GCD)](./GCD.c) | Time - **O(log10(min(m, n)))**
Space - **O(1)** |
**Will keep adding more programs.**