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.