algorithmrecursion# Problem in thinking recursively. How to take recursive leap of faith?

The common guidelines I follow to solve problems recursively is do divide the problems in subproblems and solve for the smaller inputs. If it works, it would work for bigger inputs as well (*Recursive leap of faith*).

So with I tried solving this problem. Find all subsets of an `arr`

;

For e.g if arr = [1, 2, 3]

The output should be:

[3, 2, 1] [2, 1] [3, 1] [1] [3, 2] [2] [3] []

So the way I thought was to divide this in smaller problems.
for e.g `f(n) = {arr[0], {f(arr[0], f(n-1)} }`

and came up with this solution:

```
var res = [];
function recur(arr){
if(arr.length === 1) {
return arr[0];
}
for(let elem of arr){
res.push(elem);
res.push([elem, recur(arr.filter(k=> k!== elem))]);
}
return res;
}
console.log(recur([1,2]))
```

Now while this works for smaller inputs lime `[1]`

or `[1, 5]`

It's certainly a *wrong* solution and it wouldn't work for other inputs.

The correct solution would be something like this:

```
function recur(arr, ind=0, res=[]){
function subsequence(arr, ind=0, res=[]){
if(ind === arr.length){
console.log(res);
return
}
subsequence(arr, ind+1, [arr[ind], ...res]);
subsequence(arr, ind+1, res);
}
subsequence(arr, ind, res)
}
recur([1,2,3],0, []);
```

Now here are my questions:

- Am I wrong to follow the above guidelines as it is or have I misinterpreted?
- Are there any finite list of patterns which I can practice to be able to solve any kind of recursive problems or the pattern is just endless

Solution

To answer your questions:

- I would formulate the "recursive leap of faith" differently:
*Assuming*you have correct solutions to the subproblems, how can you "combine" them to a correct solution of the "whole" problem? This is how you come up with the "recursion". Then you just need to figure out the "base case" (solution to the trivial problem), verify that the step indeed reduces to the base case, and you're good. - No, there is no finite list of patterns. All problems
*can*be solved "recursively" (purely functionally), so if there was a simple list of patterns, algorithm design would be a solved problem, but it isn't. You're never "done" learning. (Within the scope of a course however, you can usually expect your problems to be simple enough and somewhat similar to practice problems, such that the techniques you have learnt can be used to solve them.)

Now let's look at your problem as an example: Finding all subsets of an array (represented by a set).

*Let's pretend we already have the problem solved for smaller sets*. So our array has n elements, but we have only solved the problem *somehow* for sets of size n - 1. How could we possibly take advantage of this? We need to "reduce" our problem: Let's remove an element. Then, solve the reduced subproblem for the set with one less element. We can assume that this solution is correct, taking the "leap of faith".

Now, how do we construct all subsets of the original set from this? Easy: To be subsets of our original sets, all these subsets can also contain the element we removed, or they don't.

Now what's the base case? If a set is empty, there is only one subset: The empty set.

In code:

```
function findSubsets(arr) {
if (arr.length === 0) {
return [[]] // base case
}
let smaller_arr = [...arr] // copy array
let element = smaller_arr.pop() // reduce problem by removing an element
// this recursive call is where we take the "leap of faith"
let subsets_of_smaller_arr = findSubsets(smaller_arr)
// now construct the solution to the "larger" problem from this
let subsets = [...subsets_of_smaller_arr] // all subsets of the smaller set are also subsets of this set; be careful to copy again
for (let subset_of_smaller_arr of subsets_of_smaller_arr) {
// subsets of the smaller set can additionally have the removed element added to it
subsets.push([...subset_of_smaller_arr, element])
}
return subsets
}
```

Or perhaps, for another example of a recursive algorithm, consider Merge Sort:

- The base cases are arrays of length 0 or 1, which are already sorted.
- Merge Sort splits the array into two halves, recursively calling itself to sort the two halves. The
*recursive leap of faith*here is that we assume that these recursive calls work correctly. - Merge Sort then
*merges*these two sorted arrays into one sorted array. This can only be done efficiently*because*we can assume them to be sorted.

The common guidelines I follow to solve problems recursively is [to] divide the problems in subproblems and solve for the smaller inputs. If it works, it would work for bigger inputs as well (Recursive leap of faith).

You need to be careful here: Your "base cases" are where you "solve for smaller inputs" when designing a recursive algorithm. Your *recursion* / "dividing" the problem and then "combining" solutions *must work for problems of any size (that are not base cases)* (and assuming the solutions to the subproblems are correct).

If you're all out of ideas, you can try to come up with a *recursion* by looking at and solving small problems, *but then you need to verify that it generalizes (works for all problems of size larger than the base case)* (which in this case it doesn't).

As an exercise, I recommend you to devise *another* recursion for finding all subsets of an array: Instead of taking out a single element, you can also *split the array in the middle* and *recursively find the subsets of the two halves*, then "merge" the two by going through all combinations of these two subsets. Try to implement this, and convince yourself of its correctness.

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array