recursion Flashcards
how to solve josephus problem?
how to get all permutations for a string?
Input : str = “ABC”
Output : ABC ACB BAC BCA CAB CBA
Idea: We iterate from first to last index. For every index i, we swap the i-th character with the first index. This is how we fix characters at the current first index, then we recursively generate all permutations beginning with fixed characters (by parent recursive calls). After we have recursively generated all permutations with the first character fixed, then we move the first character back to its original position so that we can get the original string back and fix the next character at first position.
public class Permutation
{
public static void main(String[] args)
{
String str = "ABC";
int n = str.length();
Permutation permutation = new Permutation();
permutation.permute(str, 0, n-1);
}
/**
* permutation function
* @param str string to calculate permutation for
* @param l starting index
* @param r end index
*/
private void permute(String str, int l, int r)
{
if (l == r)
System.out.println(str);
else
{
for (int i = l; i <= r; i++) {
str = swap(str,l,i);
permute(str, l+1, r);
str = swap(str,l,i);
}
}
}
/**
* Swap Characters at position
* @param a string value
* @param i position 1
* @param j position 2
* @return swapped string
*/
public String swap(String a, int i, int j)
{
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i] ;
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}
}
https://www.geeksforgeeks.org/print-all-permutations-of-a-string-in-java/
Which one is Better-Tail Recursive or Non Tail-Recursive?
The tail-recursive functions are considered better than non-tail recursive functions as tail-recursion can be optimized by the compiler. The idea used by compilers to optimize tail-recursive functions is simple, since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use.
what is tail recursion?
A recursive function is said to be following Tail Recursion if it invokes itself at the end of the function. That is, if all of the statements are executed before the function invokes itself then it is said to be following Tail Recursion.
Given a set represented as a string, write a recursive code to print all the subsets of it. The subsets can be printed in any order.
Examples:
Input : set = “abc”
Output : “”. “a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”
Input : set = “abcd”
Output : “” “a” “ab” “abc” “abcd” “abd” “ac” “acd”
“ad” “b” “bc” “bcd” “bd” “c” “cd” “d”
The idea is to consider two cases for every character. (i) Consider current character as part of the current subset (ii) Do not consider current character as part of the current subset.
https://www.geeksforgeeks.org/recursive-program-to-generate-power-set/
print 1 to n using recursion
class GFG {
public static void main(String[] args)
{
printNos(1, 100);
}
public static void printNos(int initial, int last)
{
if (initial <= last) {
System.out.print(initial + " ");
printNos(initial + 1, last);
}
}
}
it is tail recursion, so it is better than calling recursive method befo
how to calculate sum of digits using recursion?
The step-by-step process for a better understanding of how the algorithm works.
Let the number be 12345.
Step 1-> 12345 % 10 which is equal-too 5 + ( send 12345/10 to next step )
Step 2-> 1234 % 10 which is equal-too 4 + ( send 1234/10 to next step )
Step 3-> 123 % 10 which is equal-too 3 + ( send 123/10 to next step )
Step 4-> 12 % 10 which is equal-too 2 + ( send 12/10 to next step )
Step 5-> 1 % 10 which is equal-too 1 + ( send 1/10 to next step )
Step 6-> 0 algorithm stops
following diagram will illustrate the process of recursion
~~~
static int sum_of_digit(int n)
{
if (n == 0)
return 0;
return (n % 10 + sum_of_digit(n / 10));
}
~~~
What is the base condition in recursion?
In a recursive program, the solution to the base case is provided and the solution of bigger problem is expressed in terms of smaller problems.
int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
In the above example, the base case for n < = 1 is defined and a larger value of a number can be solved by converting to a smaller one till the base case is reached.
How a particular problem is solved using recursion?
The idea is to represent a problem in terms of one or more smaller problems, and add one or more base conditions that stop recursion. For example, we compute factorial n if we know factorial of (n-1). The base case for factorial would be n = 0. We return 1 when n = 0.
Given an unsorted array of N elements and an element X. The task is to write a recursive function to check whether the element X is present in the given array or not.
Example:
array[] = {1, 2, 3, 4, 5}
X = 3.
The function should return True, as 3 is
present in the array.
Solution: The idea is to compare the first element of the array with X. If the element matches with X then return True otherwise recur for the remaining part of the array.
The recursive function will somewhat look like as shown below:
// arr[] is the given array
// l is the lower bound in the array
// r is the upper bound
// x is the element to be searched for
// l and r defines that search will be
// performed between indices l to r
bool recursiveSearch(int arr[], int l,
int r, int x)
{
if (r < l)
return false;
if (arr[l] == x)
return true;
if (arr[r] == x)
return true;
return recursiveSearch(arr, l + 1,
r - 1, x);
}
Time Complexity: The above algorithm runs in O(N) time where N is the number of elements present in the array.
Space Complexity: There is no extra space used however the internal stack takes O(N) extra space for recursive calls.
Given a string, the task is to write a recursive function to check if the given string is palindrome or not.
Examples:
Input : string = “malayalam”
Output : Yes
Reverse of malayalam is also
malayalam.
Input : string = “max”
Output : No
Reverse of max is not max.
Solution: The idea to write the recursive function is simple and similar to the above problem:
If there is only one character in the string, return true.
Else compare first and last characters and recur for remaining substring.
public static void main(String[] args) {
String input = "m";
System.out.println(recursivelyFindPalindrome(input, 0, input.length() - 1));
}
private static boolean recursivelyFindPalindrome(String input, int start, int end) {
char[] letters = input.toCharArray();
if (letters[start] == letters[end]) {
return true;
}
if (letters[start] != letters[end]) {
return false;
}
if (start > end) {
return true;
}
return recursivelyFindPalindrome(input, start + 1, end - 1);
}
