McCarthy 91 function

The McCarthy 91 function is a <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursive function</a>, defined by the <a href="/facts/Computer_scientist/DavggjGL">computer scientist</a> <a href="/facts/John_McCarthy_(computer_scientist)/ajKU4SdD">John McCarthy</a> as a test case for <a href="/facts/Formal_verification/BYD4GnJR">formal verification</a> within <a href="/facts/Computer_science/lN3pEyPz">computer science</a>.
The McCarthy 91 function is defined as

M
        (
        n
        )
        =
        
          
            {
            
              
                
                  n
                  −
                  10
                  ,
                
                
                  
                    
                      if 
                    
                  
                  n
                  >
                  100
                  
                    
                       
                    
                  
                
              
              
                
                  M
                  (
                  M
                  (
                  n
                  +
                  11
                  )
                  )
                  ,
                
                
                  
                    
                      if 
                    
                  
                  n
                  ≤
                  100
                  
                    
                       
                    
                  
                
              
            
            
          
        
      
    
    {\displaystyle M(n)={\begin{cases}n-10,&{\mbox{if }}n>100{\mbox{ }}\\M(M(n+11)),&{\mbox{if }}n\leq 100{\mbox{ }}\end{cases}}}

The results of evaluating the function are given by M(n) = 91 for all integer arguments n ≤ 100, and M(n) = n − 10 for n > 100. Indeed, the result of M(101) is also 91 (101 - 10 = 91). All results of M(n) after n = 101 are continually increasing by 1, e.g. M(102) = 92, M(103) = 93.

McCarthy 91 function open-in-new

McCarthy 91 function