Recursion in a C ++ factual program
Hi I have this piece of code which I have coded based on some other recursive and factorial programs but my problem is that I am really confused about how it stored the value and stored it and then returned it at the end
int factorialfinder(int x)
{
if (x == 1)
{
return 1;
}else
{
return x*factorialfinder(x-1);
}
}
int main()
{
cout << factorialfinder(5) << endl;
}
so 5 goes inward and gets multiplied by 4, calling its function over and over and over, then it gets one and returns the factorial response
why? I have no idea how it is stored, why is it returning 1, returning the actual response, what does it actually do?
source to share
Source: Image via: IBM Developers website
Just look at the picture above, you will understand it better. The number is never stored, but it is called recursively to calculate the result.
Therefore, when you call fact (4), the current stack is used to hold each parameter, since recursive calls happen all the way up to factorialfinder (1). Thus, the calculation looks like this: 5 * 4 * 3 * 2 * 1.
int factorialfinder(int x)
{
if (x == 1) // HERE 5 is not equal to 1 so goes to else
{
return 1;
}else
{
return x*factorialfinder(x-1); // returns 5*4*3*2*1 when x==1 it returns 1
}
}
Hope this helps.
source to share
Returning 1 does not return the actual response. It just returns the answer to the challenge
factorialfinder(1);
which is happening in your code.
In any program, the call stack is a space in memory that is used to keep track of function calls. The space from this memory is used to store the arguments to a function, as well as the return value of that function. Whenever some function A calls another function B, A gets the return value of B from that space.
A recursive function is nothing special, it is just a regular function calling another function (which is itself). So when the recursive function F calls itself, it calls another function: F calls F ', which calls F' ', which calls F' '', etc. It's just F, F '', F '' ', etc .. execute the same code, just with different inputs.
The expression if (x == 1)
should check when this process should be stopped. The return value of F '' 'is used by F' '. Return value F 'is used by F'. The return value of F 'is used by F.
In the factorial of some number, the operation is (n) * (n-1) * (n-2) * .... * ( 1 ). I have highlighted 1; this is a test condition.
source to share
A recursive function breaks down a large problem into smaller cases.
Transition according to your program:
call factorialfinder with 5, result is stored as 5 * factorialfinder(4)
call factorialfinder with 4, result is stored as 5 * 4 * factorialfinder(3)
call factorialfinder with 3, result is stored as 5 * 4 * 3 * factorialfinder(2)
call factorialfinder with 2, result is stored as 5 * 4 * 3 * 2 * factorialfinder(1)
call factorialfinder with 1, result is stored as 5 * 4 * 3 * 2 * 1
essentially it concatenates the result of the call stack into factorialfinder until you hit your base case, in this case x = 1.
source to share
Well, a factorial function can be written using recursion or not, but the main focus of recursion is that it uses the system stack, so every function call is an element on the system stack, like this (read from bottom to top):
Another consideration in the recursion function is that it has two main pieces of code:
- Base case
- Recursion case
In the basic case, a recursive function returns an element that limits the algorithm and that stops recursion. In the factorial, this element is 1 because mathematically, the factorial of the number one is 1 by definition. For other numbers, you don't know the factorial, because of this you have to calculate using a formula, and one of its implementations uses recursion, hence the recursive case.
Example: Factorial 5, procedure: 5 * 4 * 3 * 2 * 1 = 120, note that you must multiply each number from the top value to the number 1, in other words, until the base case occurs, which has a place that you already knew.
source to share
#include<iostream>
using namespace std;
int factorial(int n);
int main()
{
int n;
cout << "Enter a positive integer: ";
cin >> n;
cout << "Factorial of " << n << " = " << factorial(n);
return 0;
}
int factorial(int n)
{
if(n > 1)
return n * factorial(n - 1);
else
return 1;
}