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));
}
~~~
