Recursive program

Hi, i’m having a miserable time understanding recursion , i just don’t seem to be able to think recursivly, i find it much more natural to think with loops etc, and it kind of pisses me off, i know the principle(yeahhhh-find a base case to stop- find a recursion to call itself ||| Or recursion is just a box that you open and you always find another box and need a thing to stop) i got this basics, but i just can’t think recursivly even for easy problems done with normal loops.
I even stumbled on this problem wich is easy, but doing it recursivly is just a pain(i couldn’t get it right)

Am i this dumb? i hate not being to do something or understand it, and this is sickening …
-PS DIDNT FIND A CATEGORY OR TAGS FOR THIS POST-

Hi @Tahtoh! Don’t worry, recursion is rarely trivial. Often the trick is to reduce the problem to one or more sub-problems which are small enough to be solved directly; in the case of the one you’ve linked that would be r = 1:

var array = [1, 2, 3, 4, 5];
var r = 1;

function combi(array, r) {

  if (r === 1) {

    // Simply output each element
    for (var i = 0; i < array.length; i++) {
      console.log(array[i]);
    }  
  }
}

combi(array, r);

// Output:
// 1
// 2
// 3
// 4
// 5

(I’m writing in JavaScript here; hope that’s okay.)

Now we can take into account the recursion. Usually the problem is not as trivial; but for now we can pretend it is and already got the more complex part from the recursion:

function combi(array, r, result) {

  // If there is a result availabe, insert
  // a separating space
  result = result ? result + ' ' : '';

  if (r === 1) {
    for (var i = 0; i < array.length; i++) {

      // Log the result we got earlier and append
      // the solution of the trivial problem
      console.log(result + array[i]);
    }  
  }
}

// A function call within the recursion might thus
// look like e.g.
combi([3, 4, 5], 1, '2');

// Which would output:
// 2 3
// 2 4
// 2 5

Now comes the tricky bit – how do we actually reduce the problem to the trivial one? We need to get to a point where it is; this can be done with a loop here, which recursively calls the function with the respective sub-problem of each element in the array:

function combi(array, r, result) {

  // ...

  if (r !== 1) {

    // We loop through the array and take each element as
    // a starting point for the respective sub-problem
    for (var j = 0; j <= array.length - r; j++) {

      // We call the `combi` function with the remaining
      // sub-array from the current position, reducing
      // the problem by one (i.e. r - 1) and passing the
      // result-so-far plus the current element
      combi(arr.slice(j + 1, array.length), r - 1, result + array[j]);
    }
  }
}

// For array = [1, 2, 3, 4, 5] and r = 2 that would call
combi([2, 3, 4, 5], 1, '1');
combi([3, 4, 5], 1, '2');
combi([4, 5], 1, '3');

This is calling itself until the trivial problem is reached. So putting it together:

function combi(arr, r, result) {
  result = result ? result + ' ' : '';
  
  if (r === 1) {
    for (var i = 0; i < arr.length; i++) {
      console.log(result + arr[i]);
    }
  } else {
    for (var j = 0; j <= arr.length - r; j++) {
      combi(arr.slice(j + 1, arr.length), r - 1, result + arr[j]);
    } 
  }
}

combi([1, 2, 3, 4, 5], 2);

This is the basic approach how I’d try to find a solution. But there’s no hard and fast answer how to get there; actually, practice is crucial to get the hang of it IMHE. Just don’t give up to quickly! :-)

6 Likes

<3 @m3g4p0p You my friend nailed that explanation, wish some people were explaining as good as you, instead of taking into account that everyone understands every step.
Do you have some key problems i need to get my hands dirty on?
Thanks

1 Like

Glad I could help! :-) Yeah the article above seems to be more concerned with technical details such as duplicate entries, rather than with the underlying idea itself. Many thanks for your kind words anyway!

As for key problems… how about a tree search? Considering a multidimensional array such as

var tree = [
  [
    [1, 2],
    [3, 4],
    [
      [5, 6],
      [7, 8, 9]
    ]
  ],
  [
    10,
    [11, 12]
  ]
];

you could write a function find(tree, number) that recursively walks down the tree to check if a given element exists. The trivial sub-problem would be searching a flat array.

This algorithm could then be extended quite a bit; e.g. instead of just returning true you could return the index stack (such as find(tree, 9) would return [0, 2, 1, 2]). Or insert a given element after the found element, and return the resulting tree. – You’d have to find a way to pass the results from recursion to recursion appropriately.

And then of course there’s the huge field of sorting algorithms. Good luck anyway! :-)

For the recursion tree you printed , i don’t know whats the actual goal behind the question and the printed input [0.2,1,2], if you could explain the principle and i’ll try and do it for you, Thanks

@m3g4p0p Hello bro, i just stumbled on a similar problem that you solved, kind of :@
I tried doing it myself and this time i did something xd, maybe its not a good methodology but its my first time writing something recursive even if it doesnt work, this time the goal is this http://www.spoj.com/problems/ACODE/
I have commented the parts i didnt quiet understand how to get them but i hope my logic is kinda easy,and if not please correct me .
Here is the code

    #include <iostream>
    #include <string>
    using namespace std;
    auto combinaison(string low,string high,int k){
        //base case: we get to k==1 we return the string in that position
        //or if the last part is lower then 26
        k=2;
    
    for(int i=0;i<sizeof(input);++i)
        {
            if(low<26){//if the first two numbers are lower then 26, we go
            combinaison(input.substr(i,k),input.substr(i+k,i-i),k)
            k--;
            }
            else{
                combinaison(input.substr(i+1,k),input.substr(i+1+k,i-i),k)    
            }
            //memorize the number of steps
        }
    }
int main() {
    // your code goes here
    string input="25114";//needs to print 6

    return 0;
}``

Thanks again, and i know i need to train more, wich im not doing xd

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.