Recursion has always been imaginative to me. How do I write the recursive function so that it solve the problem, what all cases it would uncover as recursion progress. As input value increases things gets complex and I am lost.

To understand it better I was looking around internet and I found very ordinary yet powerful statement.

Functions can call other functions – this is a fact that most programmers know. Recursion is simply a special case where instead of calling another function, a function calls itself.

This is pretty good insight. This statement helps you to forget imaging the complex cases where you have high input value, what happens behind the scenes and so on.

Lets take an example

Write a function, for a given number, print out all different ways to make this number, by using addition and any number equal to or smaller than this number and greater than zero.

For example, given a 5, we have the following different ways to make up 5:
1st 1, 1, 1, 1, 1
2nd: 1, 4
3rd : 1, 1, 1, 2
4th : 1, 1, 3
5th : 2, 3
6th : 1, 2, 2
7th : 5

There are two ways of thinking about this problem
1. 1 + 1 = 2
2. 2 = 1 + 1

You would be wondering they both look pretty same. They both are same when result matters but they are different in approach.

Lets consider input as 3
Using approach 1, 3 be written as 1 + 1 + 1
But, using approach 2, 3 will be written as 3 = 1 + 2 and now how 2 can be written. Yes, 2 = 1 + 1

Finally, 3 = 1 + 2 = 1 + (1 + 1)
4 = 1 + 3 = 1 + (1 + 2) = 1 + (1 + ( 1 + 1))
and so on….

We can clearly see recursion pattern forming here. In this case now all we need to worry is given input just subtract 1 and call the same function again.

 
  #include <iostream>
  
  using namespace std;
  
  void printSeq(int num, int a[], int opIndx,int s){
      if(num <= 0){
          // Display the result
          for(int j=0;j<opIndx;j++)
             cout<<a[j]<<",";
         cout<<endl;
         return;
     }
 
     a[opIndx] = 1;
     // Call the function again, remember 3 = 1 + 2
     printSeq(num-1, a, opIndx+1, 1);
 }
 
 int main(){
     int a[5];
     printSeq(5,a,0,1);
     return 0;
 }

We just saw case 1 but there are other combinations of 5. Lets consider the next combinations which are
5 = 2 + (3). Later 3 will have its own combinations which don’t need to bother.
5 = 3 + (2)
5 = 4 + (1)
5 = 5 + (0)

 
   #include <iostream>
   
   using namespace std;
   
   void printSeq(int num, int a[], int opIndx,int s){
       if(num <= 0){
           //Display the output
           for(int j = 0; j < opIndx; j++)
              cout << a[j] << ",";
          cout << endl;
          return;
      }
  
      // s starts from 1 and later it will change to
      // 2, 3, 4, 5.
      // It is the case$
      // 5 = 2 + (3)
      // 5 = 3 + (2)
      // 5 = 4 + (1)
      // 5 = 5 + (0)
      for(int i = s; i <= num; i++){
          a[opIndx] = i;
          printSeq(num-i, a, opIndx + 1, i);
      }
  }   
  
  int main(){
      int a[15];
      printSeq(5, a, 0, 1);
      return 0;
  }

References
Recursion on reddit