Solved

# Recursion

Posted on 1998-04-08
167 Views
I know what this function will do, but I do not comprehend
why.
1   int factor(int x)
2   {
3       if (x==10)
4           return 1;
5       else
6       {
7           x *= factor(x - 1);
8           return x;
9       }
10  }

0
Question by:program
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 1

Accepted Solution

vsinha earned 50 total points
ID: 1184159
I am assuming x >= 10

rewriting your function to make it simpler
int factor(int x)
{
if (x==10)
return 1;
else
return x * factor(x - 1);
}

factor(10) = 1
factor(11) = 11 * factor(10) = 11 * 1 = 11
factor(12) = 12 * factor(11) = 12 * 11
factor(13) = 13 * factor(12) = 13 * 12 * 11
factor(14) = 14 * factor(13) = 14 * 13 * 12 * 11
factor(15) = 15 * factor(14) = 15 * 14 * 13 * 12 * 11

let me know if you don't understand anything, or if I have misunderstood you.
0

LVL 22

Expert Comment

ID: 1184160
Its unusual that it stops at 10 and not 1.  Ussually the line

if (x == 10)

would be

if (x == 1)

The recursive algorithm just says:  Given a number, If the number is one (10?) then factor of the number is one.  For any other number,  factor of the number is the number times factor of one less than the number.  This process continues calling factor recursivly using a number one less each time until it calls it with a value of 1 (10?).  Then the innermost factor call returns (it returns 1) which the caller multiplies by 2 and then returns.  Which the caller multiplies by 3 and then returns and so on until the outermost call returns.
0

LVL 1

Expert Comment

ID: 1184161
Actually I think to calc. the factorial the safest soln. would be to replace:
if (x == 10)
by
if (x <= 1)

but this would depend on what you want to do in the function.
0

LVL 84

Expert Comment

ID: 1184162
I'd say
if( x==0 )
(-1)! is supposed to blow up

0

Author Comment

ID: 1184163
I misstyped the line: if(x==10). It is supposed to be: if(x==1),
like nietod & vsinha mentioned. All appologies. Could I please
get a new explanation.
0

LVL 1

Expert Comment

ID: 1184164

your func. can be written as:
int factor(int x)
{
if (x==1)
return 1;
else
return x * factor(x - 1);
}

for small values:
factor(1) = 1
factor(2) = 2 * factor(1) = 2 * 1
factor(3) = 3 * factor(2) = 3 * 2 * 1
factor(4) = 4 * factor(3) = 4 * 3 * 2 * 1
factor(5) = 5 * factor(4) = 5 * 4 * 3 * 2 * 1

the best way to think of it is how factorial is defined normally:
n! = n * (n-1)!            except for n=1 where 1! = 1
0

Author Comment

ID: 1184165
Thank you much vsinha for the clear explanation of this
function.
0

LVL 1

Expert Comment

ID: 1184166
You are welcome
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. â€¦
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the bâ€¦
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Botâ€¦
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
###### Suggested Courses
Course of the Month9 days, 4 hours left to enroll