Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I am working through the Programming Paradigms via Mathematica (A First Course) and am attempting to answer the following:

Use recursion to count how many times the argument can have its square root taken before the result is less than 2: "manySqrt[x_Real]" should report how many times the "Sqrt[]" function has to be applied to "x" before the result is less than 2. For instance, Sqrt[81.0] is 9.0, Sqrt[9.0] is 3.0 and Sqrt[3.0] is less than 2 so, "manySqrt[81.0]" is 3. Of course, don't use a logarithm.

Additionally:

First, use of a repetition function ("Map[]", "MapThread[]", "Nest[]", "NestList[]", "Fold[]", "FoldList[]", "Table[]", "Apply[]", and so on, being our "adverbs") will generally disqualify a method as purely recursive, for the repetition is accomplished externally from the nested function calls. Also, repetition accomplished with a loop structure, such as a "While[]", a "Do[]", or some other repetition command, is explicitly forbidden.

My strategy is to make a list of 'Real' values and then count the 'Real' values in the list. I can get the following to work:

Clear[manySqrt]
manySqrt[x_Real] := If[x >= 2, Flatten[Append[{x}, manySqrt[Sqrt[x]]]]]

 manySqrt[81.]

(* {81., 9., 3., Null} *)

 Count[%, _Real]

(* 3 *)

However I get an erroneous answer when I try to wrap Count as follows:

Clear[manySqrt]
manySqrt[x_Real] := 
 If[x >= 2, Count[Flatten[Append[{x}, manySqrt[Sqrt[x]]]], _Real]]

 manySqrt[81.]

 (* 1 *)

I would appreciate a point in the right direction.

share|improve this question
2  
Your new function is outputting the Count[ ] instead of the new square root (presumably that's what the "1" is in the answer). –  bill s Jun 8 '13 at 15:01
    
@bills, Let me use this as a ‘learnable’ moment. My understanding was that Flatten[Append[{x}, manySqrt[Sqrt[x]]]] produced a list of real numbers; so that if I wrapped Count … _Real around it, Count would count the number of real numbers in that list. But from what I gather you are telling me is that Count actually only counted the number of times Count was invoked. Am I understanding that correctly? –  Clif Jun 8 '13 at 15:54
3  
I think rm -rf described below in great detail what is happening in your second attempt -- the output of the function is the count, not the square roots... as it was in your first attempt. Using rm -rf's definition, try Trace[manySqrt[81.]] and you can follow exactly how the function is working. –  bill s Jun 8 '13 at 16:11
add comment

5 Answers 5

up vote 6 down vote accepted

Since you're learning, it'll be instructive to know why your solution didn't work. For that, let's try replacing Count with count (note the lower case c), which doesn't have any definitions attached with it (clear it first if you have) and evaluate the function:

ClearAll[manySqrt2, count]
manySqrt2[x_Real] := If[x >= 2, count[Flatten[Append[{x}, manySqrt2[Sqrt[x]]]], _Real]]

manySqrt2[1000.] (* test *)
(* count[{1000., count[{31.6228, count[{5.62341, 
       count[{2.37137, Null}, _Real]}, _Real]}, _Real]}, _Real] *)

So you can see that the eventual solution is a final "count" of the individual counts, not the square root values at each recursion (which is what you tried to do). Since the output of Count is an Integer, the final evaluation will always be of the form:

Count[{Real, Integer, Integer, Integer, ..., Null}, Real]

which is always 1.

In general, it is always good to approach recursive definitions by first defining a "stopping condition". For instance, your solution does not return anything (or returns Null) for input < 2, when it should return 0. I would've written the definition as

ClearAll[manySqrt]
manySqrt[x_Real] /; x < 2 = 0;
manySqrt[x_Real] := 1 + manySqrt[√x]

I find this much more readable and maintainable than the If based approach, because it is immediately clear what the function does and it is easily extendable to more than one criterion.

share|improve this answer
    
"more than one criterion" - I guess the choice of using multiple definitions or Which[]/Switch[] is a matter of taste, but you're right that in recursive solutions, one should always think about the "base case" first, and build from there. –  J. M. Jun 8 '13 at 16:02
    
@rm -rf, Thank you for showing me what I did wrong as well as a code that accomplished what I wanted. I’ll add that running Trace (as @bills suggested) was illuminating. –  Clif Jun 9 '13 at 13:02
add comment

I'd have done it this way:

manySqrt[x_Real] := If[x < 2, 0, 1 + manySqrt[Sqrt[x]]]
share|improve this answer
2  
I'd rather set x_?NumericQ or x_?Positive instead of x_Real. –  Artes Jun 8 '13 at 15:21
1  
Me too, but the problem statement demanded manySqrt[x_Real], so here we are. :) –  J. M. Jun 8 '13 at 15:22
    
@0x4A4D, Very nice and compact code, thank you for the help. –  Clif Jun 9 '13 at 13:03
add comment

As in my last answer I suggest an implementation which has one detail per line for readability

sqrtCount[x_] := sqrtCount[x, 0];
sqrtCount[x_ /; x >= 2, c_] := sqrtCount[Sqrt[x], c + 1];
sqrtCount[_, c_] := c

c is the recursion count and the rest should be obvious then.

share|improve this answer
    
will try to remember ‘one detail per line’ in the future. Thank You again for your help. –  Clif Jun 9 '13 at 13:00
add comment
manySqrt[x_Real /; x >= 2] := manySqrt[Sqrt[x]]    
manySqrt[x_Real] := "below"

Trace[manySqrt[81.], Sqrt[_]]

{{Sqrt[81.]},{Sqrt[9.]},{Sqrt[3.]}}

Length@%

3

share|improve this answer
    
Thanks for working on the question. –  Clif Jun 9 '13 at 13:02
add comment

Either this or this answer is the way I would do it, but in the spirit in which solution in the question began, here's a way to use Count:

manySqrt[x_Real, f_: Count] := If[x >= 2, f[{x, manySqrt[Sqrt[x], # &]}, _Real, Infinity]]

Strictly speaking, this is not a declaration of the form manySqrt[x_Real], but manySqrt[81.0] does return 3 and so forth.

share|improve this answer
    
I would say that is a valid way do this, whether the prof(s) that taught the class back in the day would have I don’t know, anyway thank you for the answer. –  Clif Jun 9 '13 at 12:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.