Recursion(Part 1)

In this article I will speak about one of the main topics in computer science and I will write some examples to make you know what is that and how you should use it.

 Recursion function it’s a function call itself.

And this function is consisting of three parts (Base Case, some Logic, Sub-problem).

1-Base case: this is a case when it happens this recursion function should stop and gave you the result.   

2- some Logic: which happens when function called himself.

3- Sub-problem: in this part, the function calls itself by part of it but this calling should never go to infinity.

Ex1:

void SayHello(int num)

{

    if(num < 1)                                                               // Base Case

                        return;

 

    cout<<"Hello.\n";                 // Some logic

 

    SayHello(num - 1);               // Sub-problem - never go to infinity

}

Ex2

int Fact(int n)

{

            if(n <= 1)

                        return 1;

 

            return n * Fact(n-1);

}

EXPLANATION

Fact(4)

            4* Fact(3)

                        3* Fact(2)

                                    2* Fact(1)

                                    2* 1 <-- 2

                        3* 2 <-- 6

            4* 6 <-- 24

EX3

void Triangle(int x) {

   if (x <= 0) return;

   Triangle(x - 1);

   for (int i = 1; i <= x; i++)

        cout << "*";

   cout << endl;

}

 

 

EXPLANATION

Call Triangle(7)

Triangle(7)

  Triangle(6)

    Triangle(5)

      Triangle(4)

        Triangle(3)

          Triangle(2)

            Triangle(1)

              Triangle(0) <-- base case

            Triangle(1) <-- prints 1 star & new line

          Triangle(2) <-- prints 2 stars & new line

        Triangle(3) <-- prints 3 stars & new line

      Triangle(4) <-- prints 4 stars & new line

    Triangle(5) <-- prints 5 stars & new line

  Triangle(6) <-- prints 6 stars & new line

Triangle(7) <-- prints 7 stars & new line

 

The output will be:

*

**

***

****

*****

******

*******

Ex4

 3n+1 Series:  Next(n): if n is odd then n = 3 *n +1.    If n is even then n = n/2.   if n == 1, stop

E.X. 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Given n, find length of 3n+1 sequence. E.g. F3n_1(22) = 16

 

int F3n_1(int n)                       // Recursion State: n

{

            if(n == 1)

                        return 1;

            if(n%2 == 0)

                        return 1 + F3n_1(n/2);            // 1+ as we have an element in the sequence

            return 1 + F3n_1(3 *n + 1);

}

   


Comments

Post a Comment

Popular posts from this blog

Leet code (Reverse Integer)

  7.   Reverse Integer Given a signed 32-bit integer  x , return  x  with its digits reversed . If reversing  x  causes the value to go outside the signed 32-bit integer range  [-2 31 , 2 31  - 1] , then return  0 . Assume the environment does not allow you to store 64-bit integers (signed or unsigned).   Example 1: Input: x = 123 Output: 321 Example 2: Input: x = -123 Output: -321 Example 3: Input: x = 120 Output: 21 Example 4: Input: x = 0 Output: 0   Constraints: -2 31  <= x <= 2 31  - 1 Solution class Solution { public:     int reverse(int x) {         int rev = 0;         while (x) {             int pop = x % 10;             x /= 10;             if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;           ...
Read more

Graph Theory(adjacency matrix,adjacency list)

Image
today I will speak about one of the most important topics which are graph theory. I will take a long time in this series because I wanna speak a lot of data structure related to graph theory but in the beginning, I will speak about just two representations which are  (adjacency matrix, adjacency list). adjacency matrix the first let's talk about adjacency matrix .this to make a memory representation for any graph (directed or non-directed) we can imagine that Like  code bool adjacency_matrix[100][100];        Example n=3 0 1 0 1 1 0 0 1 1 for(int i=0;i<n;i++) for(int j=0;j<;j++){ int x; cin>>x; adjacency_matrix[i][j]=x; } adjacency list then I will speak about adjacency list, how to represent it in memory and how we implement it with code code vector< vector<int> > adjList1;               if adjacency list without  weight vector< vector< pair<int, int> ...
Read more