Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Recursion

Posted on 1998-04-08
8
Medium Priority
?
170 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
[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
  • Learn & ask questions
8 Comments
 
LVL 1

Accepted Solution

by:
vsinha earned 200 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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
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

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
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…

610 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