Solved

Recursion

Posted on 1998-04-08
8
165 Views
Last Modified: 2010-04-10
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
Comment
Question by:program
8 Comments
 
LVL 1

Accepted Solution

by:
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

by:nietod
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

by:vsinha
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
3 Use Cases for Connected Systems

Our Dev teams are like yours. They’re continually cranking out code for new features/bugs fixes, testing, deploying, testing some more, responding to production monitoring events and more. It’s complex. So, we thought you’d like to see what’s working for us.

 
LVL 84

Expert Comment

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

0
 

Author Comment

by:program
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

by:vsinha
ID: 1184164
rewording, my previous answer:

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

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

Expert Comment

by:vsinha
ID: 1184166
You are welcome
0

Featured Post

Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

Question has a verified solution.

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

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
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.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

810 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question