#include "stdafx.h" #include <iostream> using namespace std; int factr(int n); int fact(int n); int main() { // Use recursive version. cout << "factorial is " << factr(4); cout << "\n"; // Use iterative version. //cout << "4 factorial is " << fact(4); cout << "\n"; return 0; } // Recursive version. int factr(int n) { int answer; if(n==1) {return(1);} answer = factr(n1)*n; //Execute a recursive call to factr(). cout << answer << " "; return(answer); } //Iterative version. int fact(int n) { int t, answer; answer = 1; for(t=1; t<=n; t++) {answer = answer*(t);} return(answer); }
10 Replies  1353 Views  Last Post: 14 December 2009  12:51 AM
#1
Understanding Recursive Functions
Posted 12 December 2009  06:19 PM
Replies To: Understanding Recursive Functions
#2
Re: Understanding Recursive Functions
Posted 12 December 2009  06:23 PM
answer = factr(1)*n = 1*2 = 2.
factr(1) won't print anything because based on your code it just returns 1.
#3
Re: Understanding Recursive Functions
Posted 12 December 2009  08:11 PM
Like this?:
1. factr(11)*1 < why doesn't it start at zero then?
2. factr(21)*2. answer = 2 < is ignored due to the conditional statement.
3. factr(31)*3. answer = 6
4. factr(41)*4. answer = 12
5. Where is the answer of 24?
I would have thought the first pass would out put 12 as in my logic.
First pass:
1. the 4 gets passed to the factr(4) function.
2. answer = factr(41)*4
4. answer would = 12
5. the cout would then output 12 during the first pass.
Second pass:
1. the 4 gets passed to the factr(4) function.
2. answer = factr(31)*12
4. answer would = 24
5. Third pass is ignored because 'n' would = 1.
5. the cout would then output 24 (the final value)
This post has been edited by Cyclone: 12 December 2009  08:25 PM
#4
Re: Understanding Recursive Functions
Posted 12 December 2009  08:46 PM
And your logic is backwards. It's like this.
factr(4) 4 != 1 return factr(3)*4 factr(3) 3 != 1 return factr(2)*3 factr(2) 2 != 1 return factr(1)*2 1 == 1 return 1 return 1*2 return 2*3 return 6*4 factr(4) returns 6*4 = 12 * 2 = 24
This post has been edited by ccubed: 12 December 2009  08:50 PM
#5
Re: Understanding Recursive Functions
Posted 12 December 2009  08:47 PM
begin factr(4) factr(3) factr(2) factr(1) return 1. So factr(1) = 1. print answer = 2*factr(1) = 2*1 = 2. return answer = 2. So factr(2) = 2. print answer = 3*factr(2) = 3*2 = 6. return answer = 6. So factr(3) = 6. print answer = 4*factr(3) = 4*6 = 24. return answer = 24. So factr(4) = 24. end.
This post has been edited by fushar: 12 December 2009  08:47 PM
#6
Re: Understanding Recursive Functions
Posted 12 December 2009  10:40 PM
int recursiveFactorial(int y, int x) { using namespace std; if (x <= 1) return y; //cout << y << "\t" << x << endl; y = y * x; recursiveFactorial(y, x  1); }
You want to remember that when you call the function again the y value should be updated. This is not the way it is normally programmed but it is pretty close. (Y = 1 at first.)
You could probably set up a default value of 1 for y, and then call the function again and again using two arguments.
lol were you getting infinite loops or was it returning 0.
#7
Re: Understanding Recursive Functions
Posted 12 December 2009  11:48 PM
Cyclone, on 12 Dec, 2009  05:19 PM, said:
#include "stdafx.h" #include <iostream> using namespace std; int factr(int n); int fact(int n); int main() { // Use recursive version. cout << "factorial is " << factr(4); cout << "\n"; // Use iterative version. //cout << "4 factorial is " << fact(4); cout << "\n"; return 0; } // Recursive version. int factr(int n) { int answer; if(n==1) {return(1);} answer = factr(n1)*n; //Execute a recursive call to factr(). cout << answer << " "; return(answer); } //Iterative version. int fact(int n) { int t, answer; answer = 1; for(t=1; t<=n; t++) {answer = answer*(t);} return(answer); }
Cyclone, on 12 Dec, 2009  07:11 PM, said:
1. factr(11)*1 < why doesn't it start at zero then?
2. factr(21)*2. answer = 2 < is ignored due to the conditional statement.
3. factr(31)*3. answer = 6
4. factr(41)*4. answer = 12
5. Where is the answer of 24?
It doesn't. You're always passing the value1, so when your current value of n is 2, you call
answer = factr(n1)*n;
which is
answer = factr(21)*2;. The program jumps to factr(21) function and says:
if(n==1) {return(1);}and returns the value to the previous function, the one I wrote first. So its
answer = 1*2(the first one is factr(21) and the second one is current n).It returns it to the previous function where n was 3 etc. while it reaches the top, the first function you called, with the n you've send from the main() or from wherever you called it.
It can be a bit confusing in the beginning. Just ask if you didn't get it.
This post has been edited by Mercurial: 12 December 2009  11:50 PM
#8
Re: Understanding Recursive Functions
Posted 13 December 2009  02:34 AM
Cyclone, on 13 Dec, 2009  03:11 AM, said:
Cyclone, on 13 Dec, 2009  03:11 AM, said:
3. factr(31)*3. answer = 6
4. factr(41)*4. answer = 12
5. Where is the answer of 24?
Check line 4 again:
factr(41)*4 is the same as factr(3)*4 is the same as 6 * 4; doesn't equal 12, its 24
#9
Re: Understanding Recursive Functions
Posted 13 December 2009  09:55 AM
Thank you very much...
#10
Re: Understanding Recursive Functions
Posted 14 December 2009  12:45 AM
1. Execute recursive function. n=4. Pass the value of 4 to the variable 'n'
2. Find base/bottom:
n = 4
answer = factr(n1)*n < When this statment is first read both the 'n' variables are assigned
the value of 4. Right after this the program will begin executing the
multiple iterations of the factr() function. The 'n' on the right side
will always be 4. The result of factr() will be unknown to this statement
untill all of it's iterations have been completed at which
point it's final result will be multiplied by 4(the value that 'n'
was assinged at the very begining).
Iterations of factr(n1)*n
(a) factr(41)*4
(aa) n = 3
(b ) factr(31)*3
(bb) n = 2
(c ) factr(21)*2 = 2 which is the result of the factr() in line (b )
(cc) n = 1
Base found (n = 1. Conditional statement met. Stop.) because executing the factr() function in
line © would make 'n' equal one and so the conditional statement would tell this iteration
of the function to return the value of 1. The 'return' statement is similer to the 'break' in
a for loop and so the recursive function will stop searching it's self for the bottom(last
statement)
3. Work back out\to the top:
Take the smallest possible answer from line © which is two and multiply
it by 3(from the previous statement) which will get the vaulue(result)
of line (b ) which will be 6. Now to get the result of line (a) we
need to take the result of the previous line(b ) of 6 and multiply it
by 4 to get the final answer of 24.
There are two passes. One to get to the very inner part of the recursive function and another
to work it's way back out while executing the statments. Executing them in 'steping stone'
like fasion. ex get the result from the inner most statement then use that result to get the
second inner most statement and so on.
#11
Re: Understanding Recursive Functions
Posted 14 December 2009  12:51 AM
Quote
One of the properties of recursive functions is that a given function call must wait for the following function call to complete its run before it itself can finish. A convenient metaphor would be that of Russian dolls. If you have a set of dolls within dolls and you take them apart you will first open the outermost doll, then the next, and so on till you have opened the innermost doll. Now when you put them back together, you cannot start with the outermost doll. You first must connect the innermost doll and then put it inside the next larger doll, and then connect it. Last of all you will reconnect the outermost doll around all the inner dolls. So too with recusion. You must finish the innermost function call before you can finish the next inner function call. You should see that the first function call (the outermost one) will be the last one to complete.
Thanks to all the posters for your help!
This post has been edited by Cyclone: 14 December 2009  12:51 AM
