- Introduction
- When to use Recursion
- Recursion in 3 steps
- Out Of Scope
- Factorial
- Fabonacci
- Sum of digits
- Power of a number
- GCD
- Product of an array
- Recursive range
- Reverse
- Palindrome
- First uppercase
- Capitalize Word
- Project structure
- Technologies Used
- Prerequisities
- Commands
- Contribution
- References
- Contact Information
The project uses recursion to find solution of interesting problems in which iterative approach is perhaps not the most optimal one and recursion can be used as an alternative approach.
Recursion is a way of solving problems by having a function calling itself or it solves a smaller subset of the problem. This goes on till an exit condition is reached.
Following are the cases in which one should choose recursion.
-
If we can divide the problem into smaller sub-problems
-
Algorithm to compute nth ...
-
Write code to list the n ...
-
Implement a method to compute all.
-
It is also used in data structures such as trees and graphs.
-
It is used in many algorithms (such as divide and conquer, greedy and dynamic programming).
In the case of factorial(or any recursive program in general), It can be written by performing the following three steps:
- Step 1: Recursive case - the flow
This covers the bulk of the logic and performs the computation required. In our case of factorial, it will be:
n!=n*(n-1)!
- Step 2: Base case - the stopping criteria
This covers the exit condition, otherwise the recursive call will go on forever resulting in an exception. In our case, for factorial, it will be:
0!=1
1!=1
- Step 3: Unintentional case
This covers the cases which are outside the problem scope. In our case, for factorial, it will be negative numbers since the factorial is based of positive numbers:
factorial(-1) ???
Similarly, the same logic of three steps applies for computing recursive solutions as well. Some of which are discussed below.
Since this is an beginner project in which the focus is just to learn the some basic recursion, testing is out of scope of this project.
A factorial is the product of all the positive numbers less than or equal to n. It is denoted by n!.
The formula for it is as follows:
n!=n*(n-1)*(n-2)*(n-3)*...*3*2*1
Or, in other words:
n!=n*(n-1)!
For example, 7!=7*6*5*4*3*2*1=5040.
Visual description
A fabonacci number sequence is a sequence of numbers in which each number is the sum of two preceeding numbers. The initial two numbers in this sequence are 0 and 1.
The formula for it is as follows:
f(n)=f(n-1)+f(n-2)
For example, f(5)=f(4)+f(3).
Visual description
The core idea here is to find the sum of digits of a positive integer number using recursion. For example,
10 --> 10/10 = 1 and remainder = 0
54 --> 54/10 = 5 and remainder = 4
112 --> 112/10 = 11 and remainder = 2
11/10 = 1 and remainder = 1
So, the formula for recursive function turns out to be, f(n)=n%10+f(n/10).
Visual description
The core idea here is to find the power of a positive integer number using recursion. For example,
xpowern = x*x*x*x*..(n times).*x
2⁴ --> 2*2*2*2
So, the formula for recursive function turns out to be, xpowern=x * xpowern-1.
Visual description
The core idea here is to find the Greatest Common Divisor of a positive integer number using recursion. the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers meaning that the remainder is zero. Here, the Euclidean algorithm for find GCD is modeled using recursion.
The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example,
gcd(8,12) = 4
Using Euclidean algorithm:
gcd(48,18)
--> 48/18 = 2 remainder 12
--> 18/12 = 1 remainder 6
--> 12/6 = 2 remainder 0
Hence, the GCD is 6.
So, the formula for recursive function turns out to be, gcd(a,0) = a and gcd(a , b) = gcd(b , a mod b).
Visual description
We find the product of an array which takes an array as input and return the product of all the numbers inside it using recursion. For example,
productOfArray{1,2,3,4,5}
--> {1,2,3,4} * 5
--> {1,2,3} * 4 * 5
---->{1,2,3} * 20
--> {1,2} * 3 * 4 * 5
---->{1,2,3} * 3 * 20
---->{1,2,3} * 60
--> {1} * 2 * 3 * 4 * 5
---->{1} * 2 * 3 * 20
---->{1} * 2 * 60
-->{1} * 120
---->1 * 2 * 3 * 4 * 5
---->1 * 2 * 3 * 20
---->1 * 2 * 60
---->1 * 120
---->120
So, the formula for recursive function turns out to be, productofArray(int A[], int N)=(productofArray(A, N - 1) * A[N - 1]).
Visual description
We create a function called recursiveRange which accepts a number and adds up all the numbers from 0 to the number passed using recursion. For example,
recursiveRange(5)
--> 5 + 4
--> 5 + 4 +3
--> 5 + 4 +3 + 2
--> 5 + 4 +3 + 2 + 1
--> 5 + 4 +3 + 2 + 1 + 0
So, the formula for recursive function turns out to be, f(n) = n + f(n-1).
Visual description
We create a function called reverse which accepts a string and returns a new string in reverse using recursion. For example,
reverse('java') # 'avaj'
reverse('australia') # 'ailartsua'
So, the formula for recursive function turns out to be, f(str) = f(str.substring(1)) + str.charAt(0);.
Visual description
We create a function for palindrome which accepts a string as input and returns true if it is a palindrome, otherwsie false. This is achieved via recursion.
A palindrome is a word, number, phrase, or other sequence of symbols that reads the same backwards as forwards, such as the words madam or racecar, the date/time stamps 11/11/11 11:11 and 02/02/2020, and the sentence: "A man, a plan, a canal – Panama". The 19-letter Finnish word saippuakivikauppias (a soapstone vendor), is the longest single-word palindrome in everyday use, while the 12-letter term tattarrattat (from James Joyce in Ulysses) is the longest in English.
A simple example of this method is as follows:
isPalindrome('foobar') # false
isPalindrome('tomamot') # true
So, the formula for Palindrome turns out to be, f(str) = f(str.substr[1,str.length-1]); when str.charAt(0)==str.charAt(str.length-1).
Visual description
We create a function for finding the first uppercase instance of an alphabet in a given string using recursion.
A simple example of this method is as follows:
findUppercase('transL')
-->checkCharacterAt(0)
-->if true
---->return charAt(0)
-->if false
---->findUppercase(subString(1 till endOfinpuString)
--> goto checkCharacterAt(0)
So, the formula for finding first uppercase alphabet in a string turns out to be, f(str) = f(str.substr[1,str.length-1]);.
Visual description
We create a function which capitalizes first instance of every word in a given sentence using recursion.
A simple example of this method is as follows:
capitalizeWord('i like java programming')
-->I like Java Programming
So, the formula for capitalizing first alphabet of each word in a string turns out to be, f(str) = f(str.sub[0,str.len -1])+ char.toStr(ch) AND str.sub([str.len-2,str.len-1]==SPACE) then char.toUpperCase(ch);.
Visual description
There are several packages, one for each problem, which contain the solution inside a Service class. These service classes are instantiated and called from main() inside the Execute class which can be found inside com.umer.main package.
- Java 11.
None
In order to run the program, one needs to open the project in a suitable IDE(such as Eclipse, STS, VSCode 0or IntelliJ), navigate to the Execute class inside com.umer.main package. Once there, right click---> Run As ---> Java Application.
The program currently has hard-coded values and it does not take any input from the user. However, one can go inside the main() inside Excute class and change the input parameters as one sees fit.
Feature requests, issues, pull requests and questions are welcome.
- 1: Data Structures and Algorithms from Zero to Hero and Crack Top Companies 100+ Interview questions (Java Coding) (Udemy) (Primary resource)
- 2: Factorial (Wikipedia)
- 3: Fibonacci number (Wikipedia)
- 4: Greater Common Divisor (Wikipedia)
- 5: Euclidean algorithm (Wikipedia)
- 6: Palindrome (Wikipedia)
How to reach me? At github specific gmail account.