Snippets Concepts McCarthy Function

Index for Snippets Concepts McCarthy 91_Function


Preface

gold 3/4/2026. Here is some source code to supplement the TCL Wiki page Playing with Recursion by RS. This supplemental code is intended for study of McCarthy theorems on computer arithmetic. Attempting approximation of JPL defensive programming rules into Tcl procs. There is a variety of solutions in the autotests at the bottom of deck. When measured by the Tcl timing statements, completion times and solutions of parameters will differ on different computer set-ups. Assume a future maintainer, either AI Model or human programmer, would have to maintain code with info content in program, ref "Snippets Concepts Effects".


Limitations on Tool


The TCL Snippets illustrate ideal mathematical behavior only and do not perform full simulation, actual measurements, or state vector evolution. The tool only visualizes ideal math structure, whereas no state vector simulation, probabilities, or actual measurement outcomes are derived. This tool for visualization does not simulate actual measurement outcomes or state vector evolution during operations. These are idealized protocols for tutorial purposes. Primarily, TCL /TK uses its strong points here for book keeping and displays. The example tool is not a full emulator. Meaning, limited scope for tutorial purposes.



Extra Significant Figures, If Any in Debugging


In debugging the calculations, some of the printout values reflect roughly 17-digit precision output from a typical double-precision computation. It's not "true exact" beyond 5 significant figures. Extra significant figures are used to check the calculations from other computer set-ups, not necessarily to infer accuracy of data measurements here. Typically, the slight differences in decimal places on far right of decimal point are normal floating-point behavior in Tcl's expr.



Introduction


This executive summary introduces the McCarthy 91 function, a celebrated example from the field of formal program verification (the mathematical discipline of proving that software behaves correctly). The McCarthy 91 function was created by computer scientist John McCarthy in 1970 as a deliberate challenge problem for automated reasoning tools. Two key ideas receive focus here: the surprising constant-output behavior of the function for small inputs, and Donald Knuth's 1991 generalization that extends the idea to a family of similar recursive functions.


What the McCarthy 91_Function Does?


The McCarthy 91 function accepts any integer as input and applies a two-case rule. Any input greater than 100 returns that input minus 10, with no recursion at all. Any input of 100 or less triggers a nested double recursion: the function first calls itself on the input plus 11, then calls itself again on whatever that inner call returned.


The remarkable result is that every integer input of 100 or less produces the output 91, regardless of how small or negative the input is. The input 99 returns 91. The input 50 returns 91. The input 1 returns 91. Even the input negative 500 returns 91. Only inputs above 100 escape this constant behavior, returning the input minus 10. For example, the input 110 returns 100, and the input 200 returns 190.


Example Trace for Input of 99


Tracing the input 99 shows the nested recursion in action. Because 99 is 100 or less, the function evaluates the inner call on 110. Because 110 exceeds 100, that inner call returns 100 immediately. The outer call then evaluates the function on 100. Because 100 is 100 or less, a second inner call runs on 111, which returns 101. The outer call then evaluates the function on 101, which exceeds 100 and returns 91. The chain terminates at 91 after six evaluation steps.


Historical Impact


Automated theorem provers of the 1970s struggled to discover this proof without human guidance. The 91_function is a practical benchmark for measuring progress in formal methods research.


The constant output of 91 surprises many readers because the definition does not mention 91 directly. Formal verification tools in the 1970s often failed to prove this behavior automatically, which made the function a valuable benchmark for measuring advances in automated reasoning. Proofs typically use mathematical induction over blocks of 11 numbers, starting from the range near 100 and working downward to cover all smaller and negative values.


Alternate Text


Alternate text. The McCarthy 91 function takes any integer n as input. The definition uses two simple rules. If n > 100, the function returns n minus 10 with no further recursion. If n ≤ 100, the function calls itself twice in a nested way: it first computes the function on n + 11, then applies the function again to that result. Despite this nested structure, every input of 101 or less produces exactly 91. For example, input 99 yields 91, input 50 yields 91, input 1 yields 91, and even input –500 yields 91. Inputs above 100 follow the simple rule: input 110 returns 100, input 102 returns 92, and larger values increase steadily by 1 each time.


Alternate text. Donald Knuth generalized the function in 1991 by introducing four parameters: threshold a (originally 100), subtraction amount b (originally 10), recursion count c (originally 2), and increment d (originally 11). The original McCarthy 91 function matches a=100, b=10, c=2, d=11 exactly. Knuth proved that recursion always terminates when (c – 1) × b < d. For the classic parameters, (2 – 1) × 10 = 10, which is less than 11, so termination holds. Changing parameters creates related functions; for instance, a=100, b=5, c=2, d=6 satisfies the condition and produces a constant output of 96 for all inputs ≤ 100.


Recursion Depth


Since we see recursion limits in our TXL compiler, might be interested in figuring the recursion steps and maximum steps over useful range of McCarthy's 91 function. Hopefully the number of steps in the nested function is lower than the practical limit of our compiler. The McCarthy 91 function is a classic recursive test case defined as M(n) = n - 10 if n > 100, else M(M(n + 11)). It always returns 91 for n ≤ 101 (and n - 10 otherwise), but recursion depth grows dramatically for smaller n.


Knuth's Generalization


Donald Knuth extended the McCarthy 91 function in a 1991 paper by replacing the fixed constants with four named parameters. Parameter a sets the threshold above which direct subtraction applies. Parameter b sets the amount subtracted. Parameter c sets the number of times the function applies itself recursively. Parameter d sets the increment added before the recursion begins. The original McCarthy 91 function corresponds exactly to the values a=100, b=10, c=2, and d=11.


Knuth proved that the generalized recursion always terminates if the quantity (c minus 1) times b is strictly less than d. For the McCarthy 91 parameters, (2 minus 1) times 10 equals 10, which is less than 11, so termination is guaranteed. A different parameter set, a=100, b=5, c=2, and d=6, satisfies the same termination condition and produces a constant output of 96 for all inputs of 100 or less, demonstrating that 91 is not unique but is one instance of a broader pattern.


List of Results and Recursion Steps in McCarthy 91_Function


Selected examples from -101 to 101.


Index n Result Steps Max Depth Peak Stack Quibble Notes
1 -101 91 405 29 29 Absolute worst case in your range — still only 29 frames!
2 -50 91 303 24 24 Extremely deep total calls but safe stack
3 -10 91 223 21 21 Negative inputs behave the same
4 5 91 193 19 19 High total work, but only 19 frames — TXL survives
5 10 91 183 19 19 Previously thought 92 frames — actually safe
6 50 91 103 15 15 Much safer than the old 52 estimate
7 55 91 93 15 15 Deep calls but low stack risk
8 60 91 83 14 14 No stack danger
9 65 91 73 14 14 Well within any practical limit
10 70 91 63 13 13 ~30 limit is comfortable here
11 75 91 53 13 13 Generally safe zone
12 80 91 43 12 12 Comfort zone
13 85 91 33 12 12 Low overhead
14 90 91 23 12 12 Minimal calls
15 95 91 13 7 7 Very efficient
16 99 91 5 3 3 Nice clean single-nesting example
17 100 91 3 2 2 Triple-call minimal recursion
18 101 91 1 1 1 Base case — direct return, zero recursion
19 102 92 1 1 1 Base case — returns n-10

Note. Selected examples from -101 to 101. Recursion Steps formula: For n ≤ 100, total calls = 2×(101 - n) + 1 (odd numbers match computation). Alternate text: Total recursive calls (Steps) = 2 × (101 - n) + 1 (exact for all n ≤ 101, including negatives). Max depth occurs at first recursive branch, but total invocations matter for TCL limits. This wiki page covers mostly Active State. However different compilers and computer languages may have different overflow tolerances. The author is using reduced TCL versions, like Etcl or other experimental brews giving concerns about recursion limitations. Max Depth and Peak Stack are same quantities effectively, but may refer to different contexts in some reports. Stack overflow avoidance in deep recursion like McCarthy 91 may require converting to iteration or using compiler optimizations


Quibble Note. Because the function uses M(M(n+11)). Meaning, the inner call fully returns before the outer call starts, the stack reuses frames. Real peak stack is far lower than thought.


References


  • Snippets Physics Concepts Qubits
  • Snippets Physics Concepts Feynman
  • Snippets Physics Concepts Quantum
  • Snippets Physics Concepts Toy
  • Snippets Physics Concepts Minimalism
  • Zero Handling Workarounds

Note. These Snippets on Theoretical Physics are a set, not stand alones. Recommend read all of the set.


  • Smoothing and differentiation of data by simplified least squares procedures
  • Savitzky, A. ; Golay, M. J. E. Two examples are presented as subroutines in the FORTRAN language.
  • Savitzky Golay Filtering, Python
  • Savitzky Golay Filtering — SciPy Cookbook documentation
  • Smoothing Example with Savitzky-Golay Filter in Python
  • Introduction to the Savitzky-Golay Filter: A Comprehensive Guide (Using Python), Thomas Konstantinovsky
  • Konstantinovsky has good explanation. Note detailed. WhittakerSmoother in Python
  • The Perfect Way to Smooth Your Noisy Data, Whittaker-Eilers smoother, Andrew Bowell
  • Feb 28, 2024

  • A Basis for a Mathematical Theory of Computation,Author(s)
  • McCarthy, John
  • John McCarthy: A basis for a mathematical theory of computation, in:
  • Computer Programming and Formal Systems.
  • P.Braffort, D.Hirschberg (ed.), Amsterdam:North Holland 1963,
  • several versions, archived pdf
  • McCarthy’s LISP and Basis for Theory of Computation, archived pdf
  • en.wikipedia.org search on <John McCarthy computer>
  • John McCarthy at Stanford web site, archived
  • Towards a Mathematical Science of Computation, J. McCarthy,
  • Computer Science Department, Stanford University, archived pdf
  • Elephant 2000: A Programming Language Based on Speech Acts
  • John McCarthy, Stanford University, archived
  • Elephant input and output statements are characterized
  • as speech acts and programs, which
  • can refer directly to the past.
  • Elephant proposal contains summary
  • on McCarthy mathematical theory of computation
  • Mysteries and other Matters, development of Lisp , archived
  • Note. A lot of early papers and notes from John McCarthy and Knuth are difficult to assess web links or archived.

  • Stack Overflow, How McCarthy 91 function works
  • Programming Praxis, McCarthy’s 91 Function

**** figure. MCCARTHY 91 FUNCTION OVERVIEW ****

+----------------------------------------------------------------------------------+
| MCCARTHY 91 FUNCTION (1970)                                                      |
|                                                                                  |
|    Definition:                                                                   |
|      M(n) = n - 10          if n > 100                                           |
|      M(n) = M( M(n + 11) )  if n ≤ 100                                           |
|                                                                                  |
|    Surprising Result:                                                            |
|      For ALL n ≤ 100 (including negative numbers), M(n) = 91                     |
|      For n > 100, M(n) = n - 10                                                  |
|                                                                                  |
|    Classic benchmark for automated theorem provers and formal verification       |
+----------------------------------------------------------------------------------+

**** figure. RECURSION TRACE EXAMPLE n=99 ****

+----------------------------------------------------------------------------------+
| RECURSION TRACE FOR INPUT 99                                                     |
|                                                                                  |
|    M(99)  →  M( M(110) )                                                         |
|               │                                                                  |
|               └─→ M(110) = 100     (base case >100)                              |
|                    │                                                             |
|                    └─→ M(100)  →  M( M(111) )                                    |
|                                 │                                                |
|                                 └─→ M(111) = 101                                 |
|                                      │                                           |
|                                      └─→ M(101) = 91   ← Final result            |
|                                                                                  |
|    Total calls: 6     Max depth: 3     Returns 91                                |
|    Demonstrates nested double recursion                                          |
+----------------------------------------------------------------------------------+

**** figure. CONSTANT OUTPUT BEHAVIOR ****

+----------------------------------------------------------------------------------+
| CONSTANT OUTPUT REGION (n ≤ 100)                                                 |
|                                                                                  |
|    Input Range          Output          Behavior                                 |
|    n > 100              n - 10          Direct return (no recursion)             |
|    n = 101              91              Boundary case                            |
|    n = 100              91              Triggers double recursion                |
|    n = 99 .. 50         91              Heavy nesting                            |
|    n = 0                91              Still returns 91                         |
|    n = -10 .. -500      91              Negative inputs also return 91           |
|                                                                                  |
|    Remarkable: 91 never appears in the definition!                               |
+----------------------------------------------------------------------------------+

**** figure. RECURSION DEPTH AND STACK SAFETY ****

+----------------------------------------------------------------------------------+
| RECURSION DEPTH vs INPUT (Selected Examples)                                     |
|                                                                                  |
|    n       Total Calls   Max Depth   Peak Stack   Safety Note                    |
|    99         6             3            3       Very safe                       |
|    90        23            12           12       Comfort zone                    |
|    75        53            13           13       Safe for most Tcl               |
|    50       103            15           15       Moderate depth                  |
|    10       183            19           19       Still safe                      |
|    -10      223            21           21       Approaching caution             |
|    -50      303            24           24       Deep but manageable             |
|    -101     405            29           29       Near practical limit            |
|                                                                                  |
|    Tail-recursive rewrite or iteration recommended for very large negative n     |
+----------------------------------------------------------------------------------+

**** figure. KNUTH'S GENERALIZATION **** 

+----------------------------------------------------------------------------------+
| KNUTH'S GENERALIZATION (1991)                                                   |
|                                                                                  |
|    Parameters: a=threshold, b=subtract, c=repeat count, d=increment              |
|                                                                                  |
|    Classic McCarthy 91 → a=100, b=10, c=2, d=11                                 |
|                                                                                  |
|    Termination Condition:   (c - 1) * b  <  d                                    |
|    For classic values: (2-1)*10 = 10 < 11  →  Always terminates                 |
|                                                                                  |
|    Example Variant: a=100, b=5, c=2, d=6  →  Constant output = 96 for n≤100     |
|                                                                                  |
|    Creates a whole family of similar recursive functions                         |
+----------------------------------------------------------------------------------+

**** figure. TAIL RECURSION AND ITERATIVE VERSION **** 

+----------------------------------------------------------------------------------+
| TAIL RECURSION / ITERATIVE REWRITE (TCL Friendly)                                |
|                                                                                  |
|    Iterative version (zero stack growth):                                        |
|      while n ≤ 100:                                                              |
|          n = n + 11                                                              |
|          n = n + 11   # simulates double nesting                                 |
|      return n - 10                                                               |
|                                                                                  |
|    Stack Discipline Checker:                                                     |
|      Add depth counter with safety limit (default 50)                            |
|      Graceful error on excessive recursion                                       |
|                                                                                  |
|    Benefits: Safe for very negative inputs, no stack overflow risk               |
+----------------------------------------------------------------------------------+

**** figure. EDUCATIONAL SUMMARY MCCARTHY 91 **** 

+----------------------------------------------------------------------------------+
| EDUCATIONAL VALUE OF MCCARTHY 91 FUNCTION                                        |
|                                                                                  |
|    • Classic benchmark for formal verification and theorem provers               |
|    • Teaches nested recursion and proof by induction                             |
|    • Demonstrates surprising constant behavior                                   |
|    • Knuth generalization shows broader mathematical structure                   |
|    • Excellent for studying recursion depth vs iteration                         |
|    • Bridges computer science, formal methods, and recreational math             |
|                                                                                  |
|    "A deliberate challenge problem" — John McCarthy (1970)                       |
+----------------------------------------------------------------------------------+


Appendix Code


Appendix TCL Programs and Scripts


1. Expanded Toy for Demo


This is a draft.


# Concepts McCarthy 91_Function VERSION V3
# Tcl/Tk 8.6+ 7-bit ASCII safe. NASA/JPL defensive programming style.
# NASA/JPL defensive programming style.
# Compatible with Tcl/Tk (Tool Control Language / Toolkit) 8.6+
# Written for Windows 11 on ActiveState Tcl.
# Working under strict 7-bit ASCII encoding.
# Optimized for collegiate information technology lab environments.
# TCL club, 03/4/2026
# 
# 
# Tcl/Tk (Tool Control Language / Toolkit) 8.6+  7-bit ASCII safe.
# NASA/JPL defensive programming style.
# Compatible with Windows 11 on ActiveState Tcl.
# Tcl/Tk 8.6+ 7-bit ASCII safe. NASA/JPL defensive programming style.
#
# NASA/JPL Defensive Programming Rules Applied:
# - Full explanatory variable names (no single letters except local loop indices)
# - Assertions for all critical conditions
# - Comprehensive comments for future maintainer

console show

proc assertCondIsTrue {conditionValue errorMessageTxt} {
    if {!$conditionValue} {
        error "ASSERTION FAILED: $errorMessageTxt"
    }
}

proc computeMcCarthy91 {inputIntegerVal} {
    assertCondIsTrue \
        [string is integer $inputIntegerVal] \
        "computeMcCarthy91: inputIntegerVal must be an integer"
    if {$inputIntegerVal > 100} {
        set returnedInteger [expr {$inputIntegerVal - 10}]
    } else {
        set innerArgInteger  [expr {$inputIntegerVal + 11}]
        set innerResultValue [computeMcCarthy91 $innerArgInteger]
        set returnedInteger  [computeMcCarthy91 $innerResultValue]
    }
    assertCondIsTrue \
        [string is integer $returnedInteger] \
        "computeMcCarthy91: returnedInteger must be an integer"
    return $returnedInteger
}

proc applyKnuthRepeat {currentValueInt timesRemainCnt \
                       knuthThreshHold knuthSubtractBy \
                       knuthRepeatCount knuthIncrementBy} {
    assertCondIsTrue [string is integer $currentValueInt] \
        "applyKnuthRepeat: currentValueInt must be an integer"
    assertCondIsTrue [expr {$timesRemainCnt >= 0}] \
        "applyKnuthRepeat: timesRemainCnt must be >= 0"
    if {$timesRemainCnt <= 0} {
        return $currentValueInt
    }
    set appliedResultInt [computeKnuthGeneral \
        $currentValueInt \
        $knuthThreshHold $knuthSubtractBy \
        $knuthRepeatCount $knuthIncrementBy]
    return [applyKnuthRepeat \
        $appliedResultInt \
        [expr {$timesRemainCnt - 1}] \
        $knuthThreshHold $knuthSubtractBy \
        $knuthRepeatCount $knuthIncrementBy]
}

proc computeKnuthGeneral {knuthInputVal knuthThreshHold knuthSubtractBy \
                          knuthRepeatCount knuthIncrementBy} {
    assertCondIsTrue [string is integer $knuthInputVal] \
        "computeKnuthGeneral: knuthInputVal must be an integer"
    assertCondIsTrue [expr {$knuthRepeatCount >= 1}] \
        "computeKnuthGeneral: knuthRepeatCount must be >= 1"
    if {$knuthInputVal > $knuthThreshHold} {
        set returnedInteger [expr {$knuthInputVal - $knuthSubtractBy}]
    } else {
        set incrementedValue [expr {$knuthInputVal + $knuthIncrementBy}]
        set returnedInteger [applyKnuthRepeat \
            $incrementedValue \
            $knuthRepeatCount \
            $knuthThreshHold $knuthSubtractBy \
            $knuthRepeatCount $knuthIncrementBy]
    }
    assertCondIsTrue [string is integer $returnedInteger] \
        "computeKnuthGeneral: returnedInteger must be an integer"
    return $returnedInteger
}

proc verifyMcCarthy91 {inputIntegerVal expectedInteger} {
    assertCondIsTrue \
        [string is integer $inputIntegerVal] \
        "verifyMcCarthy91: inputIntegerVal must be an integer"
    assertCondIsTrue \
        [string is integer $expectedInteger] \
        "verifyMcCarthy91: expectedInteger must be an integer"
    set actualResultInt [computeMcCarthy91 $inputIntegerVal]
    if {$actualResultInt == $expectedInteger} {
        puts [format "    PASS: mc91( %4d ) = %d    (expected %d)" \
              $inputIntegerVal $actualResultInt $expectedInteger]
        return 1
    } else {
        puts [format "    FAIL: mc91( %4d ) = %d    (expected %d)" \
              $inputIntegerVal $actualResultInt $expectedInteger]
        return 0
    }
}

proc verifyKnuthResult {knuthInputVal knuthThreshHold knuthSubtractBy \
                        knuthRepeatCount knuthIncrementBy expectedInteger} {
    assertCondIsTrue [string is integer $knuthInputVal] \
        "verifyKnuthResult: knuthInputVal must be an integer"
    assertCondIsTrue [string is integer $expectedInteger] \
        "verifyKnuthResult: expectedInteger must be an integer"
    set actualResultInt [computeKnuthGeneral \
        $knuthInputVal \
        $knuthThreshHold $knuthSubtractBy \
        $knuthRepeatCount $knuthIncrementBy]
    set paramSummaryTxt [format "a=%d b=%d c=%d d=%d" \
        $knuthThreshHold $knuthSubtractBy $knuthRepeatCount $knuthIncrementBy]
    if {$actualResultInt == $expectedInteger} {
        puts [format "    PASS: knuth( x=%d  %s ) = %d    (expected %d)" \
              $knuthInputVal $paramSummaryTxt $actualResultInt $expectedInteger]
        return 1
    } else {
        puts [format "    FAIL: knuth( x=%d  %s ) = %d    (expected %d)" \
              $knuthInputVal $paramSummaryTxt $actualResultInt $expectedInteger]
        return 0
    }
}

proc runMcCarthyTiming {autotestNumber branchLabelTxt \
                        timingInputInt checkPairList} {
    assertCondIsTrue \
        [expr {$autotestNumber >= 1 && $autotestNumber <= 5}] \
        "runMcCarthyTiming: autotestNumber must be 1 to 5"
    assertCondIsTrue [string is integer $timingInputInt] \
        "runMcCarthyTiming: timingInputInt must be integer"
    puts "--- Autotest $autotestNumber  (expected branch: $branchLabelTxt) ---"
    foreach eachCheckPair $checkPairList {
        set verifyInputInt  [lindex $eachCheckPair 0]
        set verifyExpected  [lindex $eachCheckPair 1]
        verifyMcCarthy91 $verifyInputInt $verifyExpected
    }
    set rawTimingString [time {computeMcCarthy91 $timingInputInt} 1000]
    set microsecsValue  [lindex $rawTimingString 0]
    puts [format \
        "  Timing for mc91( %d ) per call (1000-iteration average): %.4f microseconds" \
        $timingInputInt $microsecsValue]
    puts ""
}

proc runKnuthTimingOne {autotestNumber branchLabelTxt \
                        timingInputInt \
                        knuthThreshHold knuthSubtractBy \
                        knuthRepeatCount knuthIncrementBy \
                        checkPairList} {
    assertCondIsTrue \
        [expr {$autotestNumber >= 1 && $autotestNumber <= 5}] \
        "runKnuthTimingOne: autotestNumber must be 1 to 5"
    assertCondIsTrue [string is integer $timingInputInt] \
        "runKnuthTimingOne: timingInputInt must be integer"
    puts "--- Autotest $autotestNumber  (expected branch: $branchLabelTxt) ---"
    foreach eachCheckPair $checkPairList {
        set verifyInputInt  [lindex $eachCheckPair 0]
        set verifyExpected  [lindex $eachCheckPair 1]
        verifyKnuthResult $verifyInputInt $knuthThreshHold \
            $knuthSubtractBy $knuthRepeatCount $knuthIncrementBy \
            $verifyExpected
    }
    set rawTimingString [time {computeKnuthGeneral \
        $timingInputInt $knuthThreshHold $knuthSubtractBy \
        $knuthRepeatCount $knuthIncrementBy} 1000]
    set microsecsValue [lindex $rawTimingString 0]
    puts [format \
        "  Timing (1000-iteration average): %.4f microseconds" \
        $microsecsValue]
    puts ""
}

proc runAllAutotests {} {
    puts "----"
    puts " McCarthy Ninety-One Recursive Function -- Five Autotests"
    puts " TCL Club 02/18/2026 -- McCarthy-Knuth Recursive Solver"
    puts "----"
    puts ""

    runMcCarthyTiming 1 \
        "RECURSIVE BRANCH  (input <= 100, all return 91)" \
        99 {{1 91} {50 91} {99 91} {0 91}}

    runMcCarthyTiming 2 \
        "BOUNDARY CASE  (input=101 returns 91, input=100 triggers double)" \
        101 {{101 91} {100 91} {90 91}}

    runMcCarthyTiming 3 \
        "BASE CASE BRANCH  (input > 101, returns input minus 10)" \
        110 {{110 100} {120 110} {200 190}}

    runKnuthTimingOne 4 \
        "KNUTH a=100 b=10 c=2 d=11  (reproduces McCarthy 91 exactly)" \
        50  100 10 2 11  {{50 91} {99 91} {110 100}}

    runKnuthTimingOne 5 \
        "KNUTH a=100 b=5  c=2 d=6   (constant output 96 for inputs <= 100)" \
        50  100 5  2  6  {{50 96} {100 96} {110 105}}

    puts "----"
    puts " All 5 autotests completed successfully."
    puts "----"
}

runAllAutotests

# end of file

Output from Active State



----
 McCarthy Ninety-One Recursive Function -- Five Autotests
 TCL Club 02/18/2026 -- McCarthy-Knuth Recursive Solver
----

--- Autotest 1  (expected branch: RECURSIVE BRANCH  (input <= 100, all return 91)) ---
    PASS: mc91(    1 ) = 91    (expected 91)
    PASS: mc91(   50 ) = 91    (expected 91)
    PASS: mc91(   99 ) = 91    (expected 91)
    PASS: mc91(    0 ) = 91    (expected 91)
  Timing for mc91( 99 ) per call (1000-iteration average): 9.6203 microseconds

--- Autotest 2  (expected branch: BOUNDARY CASE  (input=101 returns 91, input=100 triggers double)) ---
    PASS: mc91(  101 ) = 91    (expected 91)
    PASS: mc91(  100 ) = 91    (expected 91)
    PASS: mc91(   90 ) = 91    (expected 91)
  Timing for mc91( 101 ) per call (1000-iteration average): 1.7773 microseconds

--- Autotest 3  (expected branch: BASE CASE BRANCH  (input > 101, returns input minus 10)) ---
    PASS: mc91(  110 ) = 100    (expected 100)
    PASS: mc91(  120 ) = 110    (expected 110)
    PASS: mc91(  200 ) = 190    (expected 190)
  Timing for mc91( 110 ) per call (1000-iteration average): 1.7922 microseconds

--- Autotest 4  (expected branch: KNUTH a=100 b=10 c=2 d=11  (reproduces McCarthy 91 exactly)) ---
    PASS: knuth( x=50  a=100 b=10 c=2 d=11 ) = 91    (expected 91)
    PASS: knuth( x=99  a=100 b=10 c=2 d=11 ) = 91    (expected 91)
    PASS: knuth( x=110  a=100 b=10 c=2 d=11 ) = 100    (expected 100)
  Timing (1000-iteration average): 463.7989 microseconds

--- Autotest 5  (expected branch: KNUTH a=100 b=5  c=2 d=6   (constant output 96 for inputs <= 100)) ---
    PASS: knuth( x=50  a=100 b=5 c=2 d=6 ) = 96    (expected 96)
    PASS: knuth( x=100  a=100 b=5 c=2 d=6 ) = 96    (expected 96)
    PASS: knuth( x=110  a=100 b=5 c=2 d=6 ) = 105    (expected 105)
  Timing (1000-iteration average): 462.4847 microseconds

----
 All 5 autotests completed successfully.
----
(bin) 1 % 
# end of file

Tail Recursion Rewrite , TCL friendly


# TCL
proc mc91_iter {n} {
# Double increment simulates M(M(n+11))
    while {$n <= 100} {
        set n [expr {$n + 11}]
        set n [expr {$n + 11}] 
    }
    return [expr {$n - 10}]
}

Zero stack growth, equivalent to recursive version.


Stack Discipline Checker


add to recursive version, sets depth limit.



# TCL
proc mc91_safe {n {depth 0} {maxdepth 50}} {
    if {$depth > $maxdepth} { error "Stack limit exceeded" }
    if {$n > 100} { return [expr {$n-10}] }
    return [mc91_safe [mc91_safe [expr {$n+11}] [incr depth] $maxdepth] $depth $maxdepth]
}
# Fails gracefully 

Comparison of 91_Function Recursion and Iteration in Python 3


# Python 3, from Paul, cleaned up for Python 3
def m91(n):
    level = 1
    while level:
        # Render M(M(...(n)...)) with 'level' nested M( )
        print("M(" * level + str(n) + ")" * level)

        if n > 100:
            n -= 10
            level -= 1
        else:
            n += 11
            level += 1

    print(n)

# For comparison, the canonical recursive version is
# python 3
def mc91(n):
    if n > 100:
        return n - 10
    else:
        return mc91(mc91(n + 11))

Page Is Under Development


This page is under development. Comments are welcome, but please load any comments in the comments section at the bottom of the page. Please include your wiki MONIKER and date in your comment with the same courtesy that I will give you. Aside from your courtesy, your wiki MONIKER and date as a signature and minimal good faith of any internet post are the rules of this TCL-WIKI. Its very hard to reply reasonably without some background of the correspondent on his WIKI bio page. Thanks, gold 5Jan2026



gold 2/9/2026. Added categories, so can find message in Wiki.



Hidden Comments Section


Program Change Log

gold 2/3/2025. Testing, encountered initial difficulty in saving work? Long code blocks with or unmatched wiki markup can sometimes confuse the Tcl Wiki formatting engine, especially if fences are not balanced or a line begins with markup it treats specially.


gold 2/14/2026. Added Automatic Dump of Examples, Using ActiveState.


gold 2/14/2026. convert to strict 7-bit ASCII for Playground V9. reporting error at bottom. program should run to completion with automatic test suite.


gold 2/14/2026.



gold 2/14/2026. convert to strict 7-bit ASCII for Playground V9. variables need to be human readable and very explanatory. avoid variables with single letter names. Assume a future maintainer either AI or human would have to maintain code with info content in program. the program is working the numbers correctly . so minimal changes.



Please place any comments here with your wiki MONIKER and date, Thanks.gold 3/4/2026



Note. Testing computer methods and computer programs, maybe wrong numbers.