1
$\begingroup$

Good morning.

Reading some code in a webpage, I found this expression:

X[0] = 0.5; (*edited from x to X*)
X[n_ /; 1 <= n] := X[n] = Sin[n] X[n - 1] + Cos[n]

Is this a compact form of a while loop?

Thanks in advance.

$\endgroup$
5
  • 3
    $\begingroup$ Short answer: No. This is recursion. While is iteration. But there are ways to translate between the two, so there is some abstract form of equivalence, I guess. $\endgroup$
    – lericr
    Commented Dec 7, 2023 at 22:53
  • 1
    $\begingroup$ SIde note, I assume that the x[0] should have been X[0]. $\endgroup$
    – lericr
    Commented Dec 7, 2023 at 22:57
  • $\begingroup$ Edited. So, this form of definition is the same as, say, X[Num_]:=Table[Sin[n] X[n - 1] + Cos[n],{n,1,Num}]? $\endgroup$
    – kurush
    Commented Dec 7, 2023 at 23:07
  • 1
    $\begingroup$ Also no, since it memo-izes the X[n] values as they are processed, whereas the Table will have issues (infinite recursion, since it has no stopping point). It really is pretty much specifically the recursion it specifies. There are related constructs, such as NestList which do similar calculations but are still semantically different. $\endgroup$
    – eyorble
    Commented Dec 7, 2023 at 23:11
  • 1
    $\begingroup$ To ensure that the recursion successfully halts, the argument constraint should be positive integer rather than just positive, i.e., x[0] = 1/2; x[n_Integer?Positive] := x[n] = Sin[n] x[n - 1] + Cos[n] $\endgroup$
    – Bob Hanlon
    Commented Dec 7, 2023 at 23:16

2 Answers 2

3
$\begingroup$

Not sure if this is helpful, but...

This is recursion:

XRecurse[0] = 1/2;
XRecurse[n_Integer?Positive] := Sin[n] XRecurse[n - 1] + Cos[n];

(I removed the memoization, because I assumed that wasn't relevant to the question.)

This is iteration:

XFor[n_Integer?NonNegative] :=
  Module[
    {temp, iter},
    For[
      temp = 1/2; iter = 1, iter <= n, iter++,
      temp = Cos[iter] + Sin[iter]*temp];
    temp]

This is also iteration:

XWhile[n_Integer?NonNegative] :=
  Module[
    {temp = 1/2, iter = 1},
    While[
      iter <= n,
      temp = Cos[iter] + Sin[iter]*temp;
      iter++];
    temp]

These examples may not be the best, because they highlight the verbosity of the iterative examples. But that verbosity is just an artifact of my implementation choice (I can't immediately think of simpler iterative implementations for this particular computation). The meaningful difference is that an iterative process knows everything it needs to know at each step, and each step updates its "state", whereas a recursive process defers evaluation until the entire expression is built up (and of course, the memoization "caches" results to short circuit this for later computations).

$\endgroup$
0
$\begingroup$

Okay, this might be a better example to illustrate recursion versus iteration, based on the selection sort algorithm.

SelectionSortRecursive[{}] = {};
SelectionSortRecursive[list : {__?RealValuedNumberQ}] :=
  With[
    {minPos = PositionSmallest[list]},
    Join[list[[minPos]], SelectionSortRecursive[Delete[list, List /@ minPos]]]]


SelectionSortIterative[list : {__?RealValuedNumberQ}] := SelectionSortIterative[{}, list];
SelectionSortIterative[sorted_, {}] := sorted;
SelectionSortIterative[sorted_, unsorted_] :=
  With[
    {minPos = PositionSmallest[unsorted]},
    SelectionSortIterative[Join[sorted, unsorted[[minPos]]], Delete[unsorted, List /@ minPos]]]

Both definitions use self-reference (so maybe we could say they're lexically recursive), but in execution, one is recursive and the other is iterative.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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