Lesson # 12. Recursive algorithms

Авторadmin / Опубликовано

Back
Menu

Содержание:

Theory

Sample 1: Executing Recursive Factorial by Hand (without recursion)

int factorial(int n) {
    if (n <= 0) {
        return 1;
    }
    return n * factorial(n - 1);
}
 
int main()
{
    int x = factorial(3);
    std::cout << x;
}

Sample 2: Recursive Factorial

int factorial(int n) {
    // determine if n is less than or equal to 0 or not
    if (n <= 0) {
        // if so, then just answer 1
        return 1;
    }
    //otherwise
    else {
        // compute (n-1)! , call it n_minus1_fact
        int n_minus1_fact = factorial(n - 1);
        // multiply n_minus1_fact \8n
        // the resulting product is the answer
        return  n_minus1_fact* n;
    }
  }
 
int main()
{
    int x = factorial(3);
    std::cout << x;
}

Labs and tasks

Lab 1: Simple recursion
To do: You should calculate the numbers between x and y, which are entered by user. You are given a code how to do it without recursion, just using loop. You should transfer this code to complete the task, using recursion.

Expected output:

Enter x and y, x<y
2 4
Sum = 9

✍ How to do:

  1. Create an empty console application.
  2. Type the following code to complete the task without recursion and test it:
    3. int main()
{
    int x,y;
    std::cout << "Enter x and y, x<y";
    std::cin >> x;
    std::cin >> y;
    
    int sum = 0;
    for (int i = x; i <= y; i++) {
        sum += i;
    }
    std::cout << "Sum = " << sum;
}
  3. After, comment this code out, using /* ... */. We don't need this code anymore.
  4. Create a function called recursive_sum with two parameters, they are x and y.
    5. int recursive_sum(int x, int y) {
}
  5. In order not to make an infinite repetition of the recursive function we need to place the condition there, it is called base case:
    6. if (x == y) {
        return x;
    }
  6. The base case will break our recursion.
  7. Then, you should add the main part, the recursion. So, you should invoke the function itself:
    8. return x + recursive_sum(x + 1, y);
  8. Return to the main function and place the code to call the function after x and y initiliazing code:
    9. std::cout << "Sum = " << recursive_sum(x, y);
  9. Run the application and check the output.
Lab 2: Recursive Fibonacci sequence

To do: You should output the n-th number of Fibonacci sequence (n is a positive integer). You should complete the task, using recursion.

Note: Fibonacci sequence:

0 1 2 3 5 8 13 21...
Each specified number is the sum of two preceding numbers of the sequence.

Expected output:

enter a number:
6
6! = 8

✍ How to do:

  1. Create an empty console application.
  2. Create a function called fib with one parameter, which is n - the order of a sequence number ti output.
    3. int fib(int n) {
}
  3. In order not to make an infinite repetition of the recursive function we need to place the condition there, it is called base case. We have two of them: when n = 0 and when n = 1:
    4. if (n == 1) { 
        return 1;
    }
    else if (n == 0) {
        return 0;
    }
  4. The base case will break our recursion.
  5. After, we should create a code to output the result in the case when n > 1. In that case we should compute the sum of two preceding numbers of the sequence. In recursive meaning it means that we should invoke the same function for n-1 and for n-2 and add the results:
    6.  else if (n > 1) {
        return fib(n - 1) + fib(n - 2);
 
    }
  6. Return to the main function and place the code to input n and call the function:
    7. std::cout << "enter a number: \n";
int n;    
std::cin >> n;
std::cout << n << "! = " << fib(n);
  7. Run the application and check the output.
Back
Menu