Recursion
Topics
1. What is Recursion?
2. Problems
3. Solutions
4. Notes
Recursion
Recursion in computer science is a method where the solution to a problem depends on
solutions to smaller instances of the same problem (as opposed to iteration). The approach
can be applied to many types of problems, and recursion is one of the central ideas of
computer science.
- Most computer programming languages support recursion by allowing a function to
call itself within the program text.
- A recursive function definition has one or more base cases, meaning input(s) for
which the function produces a result trivially (without recurring).
Examples: Convert json string to object, expression evaluator with brackets
Problems
1. WAF to compute sum of numbers from 1 to n.
2. WAF to print Binary Representation of a given integer.
3. WAF to compute nth Fibonacci number.
4. Tower of Hanoi – [[Link] ] - Given a
stack of n disks arranged from largest on the bottom to smallest on top placed on a
rod, together with two empty rods, the towers of Hanoi puzzle asks for the minimum
number of moves required to move the stack from one rod to another, where moves
are allowed only if they place smaller disks on top of larger disks.
5. WAF to print interleaving of 2 strings.
6. WAF to compute xy.
Solutions and Complexity
1. WAF to compute sum of numbers from 1 to n.
int sum(int n) {
if(n == 0) return 0;
return n + sum(n-1);
}
Recurrence: T(n) = T(n-1) + 1
Time Complexity: O(n)
2. WAF to print Binary Representation of a given integer.
void binaryRepresentation(int n) {
if (n==0) return;
binaryRepresentation(n/2);
print n%2;
}
Recurrence: T(n) = T(n/2) + 1
Time Complexity: O(logn)
3. WAF to compute nth Fibonacci number.
int fibo(int n) {
if(n<=2) return 1;
return fibo(n-1) + fibo(n-2);
}
Recurrence: T(n) = T(n-1) + T(n-2) + 1
Time Complexity: O(2n)
[[Link]
rithm]
4. Tower of Hanoi [Simulation: [Link] ]
void ToH(int n, char src, char dest, char temp) {
if(n==0) return;
ToH(n-1, src, temp, dest);
printf(“Move %d from %c to %c”,n,src,dest);
ToH(n-1, temp, dest, src);
}
Recurrence: T(n) = 2T(n-1) + 1
Time Complexity: O(2n)
5. WAF to print interleaving of 2 strings.
void interleavings(char *A, char *B, char *ans, int m, int n, int idx) {
if(m==0 && n==0) {
print ans;
return ;
}
if(m != 0) {
ans[idx] = A[0];
interleavings(A+1, B, ans, m-1, n, idx+1);
}
if(n != 0) {
ans[idx] = B[0];
interleavings(A, B+1, ans, m, n-1, idx+1);
}
}
Number of Interleavings:
count(m, n) = count(m-1, n) + count(m, n-1)
count(1, 0) = 1 and count(0, 1) = 1
6. WAF to compute xy.
int power(int x, unsigned int y) {
if( y == 0)
return 1;
int z = power(x, y/2);
if (y%2 == 0)
return z*z;
else
return x*z*z;
}
Recurrence: T(n) = T(n/2) + 1
Time Complexity: O(logn)
Notes:
Fibonacci Numbers:
The Fibonacci numbers or Fibonacci sequence are numbers in the following integer
sequence:
1,1,2,3,5,8,13,21,34,55,89,144,…
Or (often, in modern usage):
0,1,1,2,3,5,8,13,21,34,55,89,144,…
By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1,
depending on the chosen starting point of the sequence, and each subsequent number is the
sum of the previous two.
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence
relation
Fn = Fn-1 + Fn-2, with seed values F1 = 1, F2 = 1 OR F1 = 0, F2 = 1
Interleavings
An interleaved string of given two strings preserves the order of characters in individual
strings. Example:
1. str1 = "AB", str2 = "CD”, Output: ABCD, ACBD, ACDB, CABD, CADB, CDAB
2. str1 = "AB", str2 = "C" , Output: ABC, ACB, CAB