## 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:__

- Create an empty console application.
- Type the following code to complete the task without recursion and test it:
- After, comment this code out, using
`/* ... */`

. We don't need this code anymore. - Create a function called
`recursive_sum`

with two parameters, they are`x`

and`y`

. - In order not to make an infinite repetition of the recursive function we need to place the condition there, it is called
**base case**: - The base case will break our recursion.
- Then, you should add the main part, the recursion. So, you should invoke the function itself:
- Return to the main function and place the code to call the function after x and y initiliazing code:
- Run the application and check the output.

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

int recursive_sum(int x, int y) { } |

if (x == y) { return x; } |

return x + recursive_sum(x + 1, y); |

std::cout << "Sum = " << recursive_sum(x, y); |

**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:__

- Create an empty console application.
- Create a function called
`fib`

with one parameter, which is`n`

- the order of a sequence number ti output. - 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`

: - The base case will break our recursion.
- 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: - Return to the main function and place the code to input
`n`

and call the function: - Run the application and check the output.

int fib(int n) { } |

if (n == 1) { return 1; } else if (n == 0) { return 0; } |

else if (n > 1) { return fib(n - 1) + fib(n - 2); } |

std::cout << "enter a number: \n"; int n; std::cin >> n; std::cout << n << "! = " << fib(n); |