### Q1. What’s recursion?

**Answer : **A recursive function is simply a function that repeatedly calls itself and the trick is to realize when to stop calling ourselves to avoid infinite loops that result in stack overflows.If the interviewers ask you to write down an algoritm that gives you the n:th fibonacci number, calculate faculty or traverse a binary tree they probably want you to provide both an iterative and recursive solution. We don’t address fibonacci in the screencast, but the formula for the n:th number is simply the sum of the previous two, i.e.

f(n) = f(n-1) + f(n-2)

Source : towfeek.se

### Q2. Can you convert this recursion function into a loop?

```
A(x) {
if x<0 return 0;
return something(x) + A(x-1)
}
```

**Answer :** Any recursive function can be made to iterate (into a loop) but you need to use a stack yourself to keep the state.

```
A(x) {
temp = 0;
for i in 0..x {
temp = temp + something(i);
}
return temp;
}
```

Source: stackoverflow.com

### Q3.How Dynamic Programming is different from Recursion and Memoization?

**Answer :**

**Memoization** is when you store previous results of a function call (a real function always returns the same thing, given the same inputs). It doesn't make a difference for algorithmic complexity before the results are stored.**Recursion** is the method of a function calling itself, usually with a smaller dataset. Since most recursive functions can be converted to similar iterative functions, this doesn't make a difference for algorithmic complexity either.**Dynamic programming** is the process of solving easier-to-solve sub-problems and building up the answer from that. Most DP algorithms will be in the running times between a Greedy algorithm (if one exists) and an exponential (enumerate all possibilities and find the best one) algorithm.- DP algorithms could be implemented with recursion, but they don't have to be.
- DP algorithms can't be sped up by memoization, since each sub-problem is only ever solved (or the "solve" function called) once

Source: stackoverflow.com

### Q4. What is a good example of Recursion (other than generating a Fibonacci sequence)?

**Answer : **There are some:

- The binary tree search
- Check for a palyndrome
- Finding factorial
- Traversing the folder hierarchy of a directory tree as part of a file system
- Towers of Hanoi
- Merge sort
- Catalan numbers

Source: stackoverflow.com

### Q5.What is the difference between Backtracking and Recursion?

**Answer : **

**Recursion** describes the calling of the *same function* that you are in. The typical example of a recursive function is the factorial. You always need a condition that makes recursion stop (base case).**Backtracking** is when the algorithm makes an opportunistic decision*, which may come up to be wrong. If the decision was wrong then the backtracking algorithm restores the state before the decision. It builds candidates for the solution and abandons those which cannot fulfill the conditions. A typical example for a task to solve would be the *Eight Queens Puzzle*. Backtracking is also commonly used within *Neuronal Networks*. Many times backtracking is not implemented recursively. If backtracking uses recursion its called **Recursive Backtracking**

P.S. * Opportunistic decision making refers to a process where a person or group assesses alternative actions made possible by the favorable convergence of immediate circumstances recognized without reference to any general plan.

Source: quora.com

### Q6. Explain what is DFS (Depth First Search) algorithm for a Graph and how does it work?

**Answer : **Depth First Traversal or Depth First Search is a edge based *recursive* algorithm for traversing (visiting) all the vertices of a graph or tree data structure using a **stack**. The purpose of the algorithm is to mark each vertex as visited while *avoiding* cycles. DFS traverse/visit each vertex exactly once and each edge is inspected exactly twice. DFS is a genuinely recursive algorithm that uses stack for *backtracking* purposes, not for storing the vertex discovery "front" (as is the case in BFS).

The **DFS** algorithm works as follows:

- Start by putting any one of the graph's vertices on top of a stack.
- Take the top item of the stack and add it to the visited list.
- Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack.
- Keep repeating steps 2 and 3 until the stack is empty.

**DFS example step-by-step**:

- Considering A as the starting vertex which is explored and stored in the stack.
- B successor vertex of A is stored in the stack.
- Vertex B have two successors E and F, among them alphabetically E is explored first and stored in the stack.
- The successor of vertex E, i.e., G is stored in the stack.
- Vertex G have two connected vertices, and both are already visited, so G is popped out from the stack.
- Similarly, E s also removed.
- Now, vertex B is at the top of the stack, its another node(vertex) F is explored and stored in the stack.
- Vertex F has two successor C and D, between them C is traversed first and stored in the stack.
- Vertex C only have one predecessor which is already visited, so it is removed from the stack.
- Now vertex D connected to F is visited and stored in the stack.
- As vertex D doesn’t have any unvisited nodes, therefore D is removed.
- Similarly, F, B and A are also popped.
- The generated output is – A, B, E, G, F, C, D.

Source: techdifferences.com

### Q7. Power function: Write a function called `power`

which takes in a base and an exponent. If the exponent is 0, return 1.

**Sample:**

```
console.log(power(2, 4)); // 16
console.log(power(2, 3)); // 8
console.log(power(2, 2)); // 4
console.log(power(2, 1)); // 2
console.log(power(2, 0)); // 1
```

**Answer : ** You can think of it in terms of this example:

```
2^4 = 2 * 2^3;
2^3 = 2 * 2^2;
2^2 = 2 * 2^1;
2^1 = 2 * 2^0; // once our exponent is 0 we KNOW that the value is always 1!
```

```
console.log(power(2, 4)); // 16
console.log(power(2, 3)); // 8
console.log(power(2, 2)); // 4
console.log(power(2, 1)); // 2
console.log(power(2, 0)); // 1
function power(base, exponent){
if(exponent == 0) return 1;
return base * power(base, exponent - 1);
}
```

Output :

```
16
8
4
2
1
```

Source: codingame.com

### Q8. Write a function called `sumRange`

. It will take a number and return the sum of all numbers from 1 up to the number passed in.

**Sample:** sumRange(3) returns 6, since 1 + 2 + 3 = 6.

**Answer : **The most important thing we need for recursive solutions is a base case. There needs to be a way of exiting the loop or the function will go on forever. The base case in the below code code is that when the input is 1, return 1. Eventually the function will return 6, the correct answer

Once you understand this code move on to the next problem :

```
var output = sumRange(3)
console.log(output);
function sumRange(num){
if(num == 1) return 1;
return num + sumRange(num - 1);
}
```

Output :

`6`

Source: codingame.com