Lets assume I have a loop for Foo.
int Foo(int n)
{
if (n <= 1)
return 2;
else
return Foo(n-1) * Foo(n-2) * Foo (n-3);
}
How many call will occur If i Call Foo(3) and what would be the result...
Thanks
-
2Why don't you run it and find out?Carl Norum– Carl Norum2010-07-20 23:14:59 +00:00Commented Jul 20, 2010 at 23:14
-
I need to be able to trade this by hand i am expecting something similar to this in the exam :Dbubdada– bubdada2010-07-20 23:18:32 +00:00Commented Jul 20, 2010 at 23:18
-
7 calls: ideone.com/0LU9Tzengr– zengr2010-07-20 23:30:36 +00:00Commented Jul 20, 2010 at 23:30
-
How many calls occur? I am kind of confused...bubdada– bubdada2010-07-20 23:33:39 +00:00Commented Jul 20, 2010 at 23:33
Add a comment
|
4 Answers
Foo(3) calls Foo(2), Foo(1) and Foo(0)
Foo(1) and Foo(0) return immediately. Now apply the same logic for Foo(2), which doesn't return immediately.
To get the result, draw a tree like this:
Foo(3)
/ | \
Foo(2) Foo(1) Foo(0)
Continue drawing the tree until you have recursive calls that return immediately (for which the first if returns true), then use those results to calculate the values that are higher in the tree.
You can use the tree to figure out how many recursive calls are made too.
1 Comment
Owen S.
@bubdada: Then, to make sure you understand, try it with Foo(5). Make a note of how many times you end up invoking the function for any given input value (i.e. how many times do you end up calling Foo(0), Foo(1), Foo(2), Foo(3), Foo(4), and Foo(5)?). For extra credit, figure out a way to cut down on the duplication, given that Foo should be returning the same value given the same input.
Pass 1: Foo(3)
Pass 2: Foo(2) * Foo(1) * Foo(0)
Pass 3: Foo(1) * Foo(0) * Foo(-1) * 2 * 2
Result: 2 * 2 * 2 * 2 * 2 = 32
Comments
Foo(3) would get called 7 times.
Comments
How about:
int Foo(int n)
{
cout << "Foo(" << n << ")" << endl;
if (n <= 1)
return 2;
else
return Foo(n-1) * Foo(n-2) * Foo (n-3);
}
