#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(n-1)*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 - 1734 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(1-1)*1 <--- why doesn't it start at zero then?

2. factr(2-1)*2. answer = 2 <--- is ignored due to the conditional statement.

3. factr(3-1)*3. answer = 6

4. factr(4-1)*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(4-1)*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(3-1)*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(n-1)*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(1-1)*1 <--- why doesn't it start at zero then?**

2. factr(2-1)*2. answer = 2 <--- is ignored due to the conditional statement.

3. factr(3-1)*3. answer = 6

4. factr(4-1)*4. answer = 12

5. Where is the answer of 24?

It doesn't. You're always passing the value-1, so when your current value of n is 2, you call

answer = factr(n-1)*n;

which is

answer = factr(2-1)*2;. The program jumps to factr(2-1) 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(2-1) 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(3-1)*3. answer = 6

4. factr(4-1)*4. answer = 12

5. Where is the answer of 24?

Check line 4 again:

factr(4-1)*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(n-1)*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(n-1)*n

(a) factr(4-1)*4

(aa) n = 3

(b ) factr(3-1)*3

(bb) n = 2

(c ) factr(2-1)*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