A recursive function that always returns 91 given a natural number argument under 100

Leo Mingo

I was reading a book introducing formal verification algorithms with Haskell Discrete Mathematics with Haskell, and there I found a counter-example of inductively defined functions:

f91 :: Int -> Int
f91 x = if x > 100
        then x - 10
        else f91 . f91 $ x + 11

This recursive function is promised to return 91 if the argument ranges between 0 and 100: I hope somebody could explain to me how the algorithm of this recursive function works.

jakubdaniel

Have you seen McCarthy 91 function?

Suppose you start with a value x > 100, then the result is simply x - 10, so a value from 91 onwards.

Now suppose the value is from 90 to 100. Then f91 takes the else branch and x + 11 is between 101 and 111. The first f91 application brings all the value to the range 91 - 101; only 101 satisfies the then branch of the second application of f91, and for that the result (x - 10) is 91.

For all the other values we get the range 102 - 111 in the else branch. However the else branch applies f91 . f91 to that value; since all the values are > 100, the first f91 brings the values down to 92 - 101, of which only 101 passes the condition > 100 of the second f91 and becomes 91.

The rest of the values go through the same cycle until all become 91. Suppose you have a different interval of 11 values below 100. The f91 first brings that interval above 100 and then keeps reducing the values to 91 starting from the higher end of the interval in the same manner. Please see the proof by induction linked in the wikipedia page.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

C - Check if given argument is natural number

Recursive Function Always Returns False

Boolean recursive function always returns true

recursive lua function always returns nil

Recursive function to check if a given number is Fibonacci

Function that given a number returns the number within a range

Room Query always returns NULL when given UUID argument

Recursive function that returns the number of possible combinations

recursive function which will return number of binary ones from the given number

My recursive function to search for an element always returns nil

Prime Number between given interval using Recursive Function

recursive Function, to find even or odd digits inside given number

Natural arithmetic C++ always returns 1

My find-biggest-number Recursive function returns a discremented value

Recursive function that returns the number of numbers greater then the first index of an array

Recursive factorial function program returns 0 for large number input in C

argument concatenation in a recursive function

C - recursive function for sum of n natural numbers

How to create a function that returns the number of nodes in a tree on a given level

Function that returns the number of "superiors" for each element in a given list

Returns in a recursive function

Recursive function that returns the remainder

Function always returns 1

How to create a function that returns another function, encompassing a given argument implicitly in C?

Recursive function always returning None

Varying recursive function at given depth

Write a function that removes any properties on the given object whose values are strings longer than the given number and returns the object

Java recursive method always returns null

org.apache.commons.net.ftp.FTPClient listFiles always returns files from root directory irrespective of the pathname given in argument