8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Your new function is outputting the Count[ ] instead of the new square root (presumably that's what the "1" is in the answer). $\endgroup$ – bill s Jun 8 '13 at 15:01
  • $\begingroup$ @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? $\endgroup$ – Clif Jun 8 '13 at 15:54
  • 3
    $\begingroup$ 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. $\endgroup$ – bill s Jun 8 '13 at 16:11
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – J. M. will be back soon Jun 8 '13 at 16:02
  • $\begingroup$ @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. $\endgroup$ – Clif Jun 9 '13 at 13:02
9
$\begingroup$

I'd have done it this way:

manySqrt[x_Real] := If[x < 2, 0, 1 + manySqrt[Sqrt[x]]]
$\endgroup$
  • 2
    $\begingroup$ I'd rather set x_?NumericQ or x_?Positive instead of x_Real. $\endgroup$ – Artes Jun 8 '13 at 15:21
  • 1
    $\begingroup$ Me too, but the problem statement demanded manySqrt[x_Real], so here we are. :) $\endgroup$ – J. M. will be back soon Jun 8 '13 at 15:22
  • $\begingroup$ @J. M., Very nice and compact code, thank you for the help. $\endgroup$ – Clif Jun 9 '13 at 13:03
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ will try to remember ‘one detail per line’ in the future. Thank You again for your help. $\endgroup$ – Clif Jun 9 '13 at 13:00
1
$\begingroup$
manySqrt[x_Real /; x >= 2] := manySqrt[Sqrt[x]]    
manySqrt[x_Real] := "below"

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

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

Length@%

3

$\endgroup$
  • $\begingroup$ Thanks for working on the question. $\endgroup$ – Clif Jun 9 '13 at 13:02
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Clif Jun 9 '13 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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