Thinking Recursively

List of some of the best resources to learn Recursion, Backtracking and most importantly to start thinking recursively.

1. Recursion Basics, Solving Problems recursively, raise to the power example and mechanics of what is going to happen, Choosing a subset
Video Lecture

2. Thinking Recursively, Permute Code, More Examples, Tree of Recursive calls
Video Lecture

3. Testing with different cases, subsets, subset stratergy, Exhaustive Recursion, Recursive BackTracking, Anagram Finder, N Queens
Video Lecture

4. Backtracking Pseudocode, Sudoku Solver, Sudoku Code, Cryptarithmetic
Video Lecture

Reference: http://see.stanford.edu/see/courseInfo.aspx?coll=11f4f422-5670-4b4c-889c-008262e09e4e (Stanford Engineering Everywhere)

Print Permutations of a String

void permutation(string, string);

int main() {

permutation("","ABC");

}

void permutation(string sofar, string remaining) {

if (remaining=="") {

//Print the string sofar<<"\n";< p="">

return;

}

for (int i=0;i

permutation(sofar+remaining[i],remaining.substr(0,i)+remaining.substr(i+1));

}

}

Recursive Approach for Reversing a String

Recursive Approach for Reversing a String

Simple Approach: Take the last character + reverse(rest of the string)
Base Case: When we encounter a single character, return that character.

string reverse(string str) {
if (str.length()==1)
return str;
return str[str.length()-1]+reverse(str.substr(0,str.length()-1));
}

Codechef Puzzle: NUMGAME

So I encounter this interesting problem NUMGAME at Codechef. This is in the list of easy problems.
At first I was lost after looking the problem and could not think of how to solve it but when I came to thinking about it, it seems that it is quite easy.

Hints: (Obvious but important)

1) An odd number is always formed by the multiplication of two odd numbers.
2) If you substract an odd number from an odd number then it gives you an even number.

GCD Recursive Method

The greatest common divisor (g.c.d.) of two nonnegative integers is the largest integer that divides evenly into both. In the third century B.C., the Greek mathematician Euclid discovered that the greatest common divisor of x and y can always be computed as follows:

If x is evenly divisible by y, then y is the greatest common divisor. Otherwise, the greatest common divisor of x and y is always equal to the greatest common divisor of y and the remainder of x divided by y


private static int gcdmethod(int i, int j) {

if (i%j==0) {
return j;
}
return gcdmethod(j,i%j);
}

}