# Lesson # 12. Recursive algorithms

Дата изменения: 15 августа 2022

Содержание:

## 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; }

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;
}

4. After, comment this code out, using /* ... */. We don't need this code anymore.
5. Create a function called recursive_sum with two parameters, they are x and y.
6. int recursive_sum(int x, int y) { }
7. In order not to make an infinite repetition of the recursive function we need to place the condition there, it is called base case:
8. if (x == y) { return x; }
9. The base case will break our recursion.
10. Then, you should add the main part, the recursion. So, you should invoke the function itself:
11. return x + recursive_sum(x + 1, y);
12. Return to the main function and place the code to call the function after x and y initiliazing code:
13. std::cout << "Sum = " << recursive_sum(x, y);
14. 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) { }
4. 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:
5. if (n == 1) { return 1; } else if (n == 0) { return 0; }
6. The base case will break our recursion.
7. 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:
8.  else if (n > 1) { return fib(n - 1) + fib(n - 2);   }
9. Return to the main function and place the code to input n and call the function:
10. std::cout << "enter a number: \n"; int n; std::cin >> n; std::cout << n << "! = " << fib(n);
11. Run the application and check the output.
Вставить формулу как
Дополнительные настройки
Цвет формулы
Используйте LaTeX для набора формулы
Предпросмотр
$${}$$
Формула не набрана
Вставить