Function part 6 (Recursion 1)
Recursion is a programming technique where a function calls itself directly or indirectly. This can be used to solve problems that can be broken down into smaller, simpler problems of the same type.
Recursion can be a bit difficult to understand at first, but it is a powerful tool that can be used to solve a wide variety of problems.
Here is a simple example of a recursive function in C++:
#include <iostream>
using namespace std;
void f(int n)
{
if (n < 1)
return;
else
cout << "round:" << n << endl;
f(n - 1);
}
int main()
{
f(5);
return 0;
}
The function f(int n) is a recursive function that prints the string “round:” followed by the integer n to the console n times.
The function works by recursively calling itself to print the string “round:” followed by the integer n - 1 to the console. This process continues until n is equal to 1, at which point the function returns.
Output:
round: 5 round: 4 round: 3 round: 2 round: 1
Recursive functions can be a bit difficult to understand at first, but they are a powerful tool that can be used to solve a wide variety of problems.
You should pay attention to these 3 contents of a recursive function (base case, logic and subproblem), which are marked in the following function:
void f(int n)
{
if (n < 1)
return; //base case
else
cout << "round:" << n << endl; //logic
f(n - 1); //subproblem
}
The three contents of a recursive function are:
- Base case: The base case is a special case that is handled directly in the function without making any recursive calls. The base case is usually a simple case that can be solved directly.
- Logic: The logic of a recursive function is the code that is executed to break down the problem into smaller, simpler problems of the same type. The logic usually involves making recursive calls to the function with smaller input values.
- Subproblem: A subproblem is a smaller, simpler problem of the same type as the original problem. Recursive functions work by breaking down the original problem into subproblems and then solving the subproblems using the same recursive function.
Here is an example of a recursive function in C++ that calculates the factorial of a number:
#include <iostream>
using namespace std;
int fact(int n)
{
if (n == 0 || n == 1)
return 1;
else
return n*fact(n - 1);
}
int main()
{
cout << fact(5) << endl;
return 0;
}
The function fact(int n) is a recursive function that calculates the factorial of a number. The factorial of a number is the product of all the positive integers less than or equal to that number. For example, the factorial of 5 is 120, because 120 is the product of 1, 2, 3, 4, and 5. So, the output of our program will be 120.
The function fact(int n) works by recursively calling itself to calculate the factorial of the number one less than the input number. For example, to calculate the factorial of 5, the function would first call itself to calculate the factorial of 4. This would then call itself to calculate the factorial of 3, and so on. Eventually, the function would reach the base case, where the input number is 0 or 1. The base case is a special case that is handled directly in the function without making any recursive calls. The factorial of 0 is 1 and the factorial of 1 is also 1, so the function simply returns 1 in these cases.
Fibonacci Series
The Fibonacci sequence is a series of numbers where each number is the sum of the two previous numbers. The first two numbers in the sequence are 0 and 1, and each subsequent number is the sum of the previous two numbers.
Here is the Fibonacci sequence up to the first 10 numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
The Fibonacci sequence can be generated using the following recurrence relation:
F(n) = F(n - 1) + F(n - 2)
where F(n) is the nth number in the Fibonacci sequence.
The Fibonacci sequence has a number of interesting properties. For example, the ratio of successive Fibonacci numbers approaches the golden ratio as the numbers get larger. The golden ratio is an irrational number that is approximately equal to 1.618.
The Fibonacci sequence appears in many different areas of mathematics and nature. For example, it can be used to model the growth of a population of rabbits, the spiral pattern of a seashell, and the branching pattern of a tree.
Here are some examples of how the Fibonacci sequence is used in the real world:
- Finance: The Fibonacci sequence can be used to identify potential support and resistance levels for stock prices.
- Music: The Fibonacci sequence can be used to create musical compositions with a pleasing rhythm and structure.
- Art: The Fibonacci sequence can be used to create works of art with a balanced and harmonious composition.
- Architecture: The Fibonacci sequence can be used to design buildings and other structures that are aesthetically pleasing and structurally sound.
The Fibonacci sequence is a fascinating and versatile mathematical sequence that has many applications in the real world.
Example:
#include <iostream>
using namespace std;
int fib(int n)
{
if (n == 0 || n == 1)
return n;
else
return fib(n - 1) + fib(n - 2);
}
int main()
{
cout << fib(3) << endl;
return 0;
}
The function fib(int n) works by recursively calling itself to calculate the Fibonacci numbers of the previous two numbers. If the input number n is 0 or 1, the function simply returns the number, because the first two Fibonacci numbers are 0 and 1. Otherwise, the function returns the sum of the Fibonacci numbers of the previous two numbers.
Output:
2
