// Schundlabua posted a response to: // https://www.sololearn.com/Discuss/1111022 // Here's an interesting one: The ackermann function. // It was designed to grow super quickly - wikipedia says A(4,2) has ~20 000 digits - but it always stops and won't get stuck in a loop. It belongs to a nasty breed of recursive function (non-primitive recursive) that can't be represented well without recursion. // Note: most of this code is an implementation of // linked list used to keep track of the loop state. // The ADT class Record maintains state information // for the ack function as it loops. The A function // is the recursive version. // Import and declare random. Debugging counts to // help with the understanding of the algorithm. // A loop count for the loop method. A call count // and maximum nesting level of the recursion. import java.util.Random val random = Random() var loop = 0 var count = 0 var maxLevel = 0 // Get a random number in the range. fun rand(from: Int, to: Int) = random.nextInt( to-from+1)+from // Single node template of the linked list storing // a value of whatever type, a pointer to the // previous node, and a pointer to the next node. data class Node(var value: T, var previous: Node? = null, var next: Node? = null) // Create an iterator class allocating the list and // the current & end positions. class ListIterator(private val self: List, start: Int, private val end: Int): Iterator { private var current = start // Test to see if any more elements exist. override fun hasNext(): Boolean = current <= end // Return the value of the current element // incrementing to the next one. override fun next(): T = self[current++]!! } // ListIterator // Class providing a first in first out template for // a linked list. Updated to insert or remove // anywhere. class List { // Pointers to the head and tail of the list. private var head: Node? = null private var tail: Node? = null var size: Int = 0 private set // Create an interator over the list. operator fun iterator(): Iterator = ListIterator(this, 0, size-1) // Provide this[index] to get read access to the // value within the node in that position. Head // points at index of zero. operator fun get(index: Int): T? = // If we have a valid index, find the node. // Start with the head node and copy of the // index. While there is another node and we // haven't found the right one, decrement the // position and move down the list. Return // null or the node's value. if (index >= 0) { var node = head var position = index while (node != null && position != 0) { position -= 1 node = node.next } // while node?.value // Otherwise, the index isn't valid so return // null. } else null // Provide this[index] to get write access to the // value within the node in that position. Head // points at index of zero. operator fun set(index: Int, value: T) { // If we have a valid index, find the node. // Start with the head node and copy of the // index. While there is another node and we // haven't found the right one, decrement the // position and move down the list. if (index >= 0) { var node = head var position = index while (node != null && position != 0) { position -= 1 node = node.next } // while // If we have found the node, update it's // value. if (node != null) node.value = value; } // if } // set // Push a new value on to the tail of the list. fun push(value: T) { // Allocate the new node with the passed in value. // If the head is null, make it point to the new // node. val newNode = Node(value) if (tail == null) head = newNode // Otherwise, make the current last node point to // the new node and the new node point back at it. else { tail?.next = newNode newNode.previous = tail } // if // The tail must point to the new node in either // case and increment the size. tail = newNode size++ } // push fun insert(index: Int, value: T) { // If we have a valid index, find the node. // Start with the head node and copy of the // index. While there is another node and we // haven't found the right one, decrement the // position and move down the list. if (index >= 0) { var node = head var position = index while (node != null && position != 0) { position -= 1 node = node.next } // while // If the node was found, insert the new node // before it. if (node != null) { // Increment the size and if the previous // node doesn't exist, change the list // head to the new node. size++ val newNode = Node(value) if (node?.previous == null) head = newNode // Otherwise, the previous node must point // to the new one. else { var prev = node.previous!! prev.next = newNode newNode.previous = prev } // if // Make the node's next & previous pointer // null. newNode.next = node node?.previous = newNode // Otherwise, we were asked to insert beyond // the last element so put it at the end. } else push(value) // Otherwise, we were asked to insert at an // invalid position so put it at the end. } else push(value) } // insert // Pop the first value off the list. fun pop(): T? = // If the head is null, return it. if (head == null) null // Otherwise, decrement the size, grab the // first node, make next node the new head, // make it's previous null, make the first // node's next pointer null, and return the // value. Note: testing for null shouldn't // be needed, but head might be changed // asynchronously so it is required. else { size-- val node = head head = head?.next head?.previous = null node?.next = null node?.value } // if fun remove(index: Int): T? = // If we have a valid index, find the node. // Start with the head node and copy of the // index. While there is another node and we // haven't found the right one, decrement the // position and move down the list. if (index >= 0) { var node = head var position = index while (node != null && position != 0) { position -= 1 node = node.next } // while // If the node wasn't found, return null. if (node == null) null // Otherwise, remove the node. else { // Decrement the size and if the previous // node doesn't exist, change the list // head to the next node. size-- if (node.previous == null) head = node.next // Otherwise, the previous node must point // to the next one. else { var prev = node.previous!! prev.next = node.next } // If the next node doesn't exist, change // the list tail to the previous node. if (node.next == null) tail = node.previous // Otherwise, the next node must point // to the previous one. else { var next = node.next!! next.previous = node.previous } // Make the node's next & previous pointer // null and return the value. node.next = null node.previous = null node.value } // Otherwise, the index isn't valid so return // null. } else null // This function is called by default to print this // class so make a list of the values in the list. // An integer list will look like: [1, 2, 3]. override fun toString(): String { // Start the finished string with the open // bracket and process the list. var s = "[" var node = head while (node != null) { // Add the current node's value to the string, // move on the next node, and, if there is one, // add the comma to the string. s += "${node.value}" node = node.next if (node != null) s += ", " } // while // Return the finished string with the close // bracket. return s+"]" } // toString } // List // Create an abstract data type sealed class to // create a structure similar to C's union. You // can't convert between them, but it limits the // storage. sealed class Record{ // When both arguments are integers. class Base(val left: T, val right: T): Record() // When the second points to another instance. class Branch(val value: T, val next: Record): Record() // This function is called by default to print this // class so generate a record string. override fun toString(): String = when (this) { is Base -> "Base(left=$left, right=$right)" is Branch -> "Branch(value=$value, next=$next)" } // when } // Record // Simplify the looks of the type. typealias IntRecord = Record // Ackermann function looping implementation with // debugging. Keep tract of how many times we've // looped. fun ack(left: Int, right: Int): Int { // Create a base with our arguments, a list, and // push the base onto the list. Label our loop // for our error exit that shouldn't happen, and // start looping. val record: IntRecord = Record.Base(left, right) val list = List() list.push(record) done@ while (true) { // Count our loops, get the data to process, and, // if it exists, process it. loop++ val rcd = list[0] if (rcd != null) when (rcd) { // When the we have a base record, process it. is Record.Base -> { // If the left integer is zero, the result // to return is the right+1. if (rcd.left == 0) { // Calculate the result and display the // debugging. The base element is done // so toss it. Get the branch to update. // If there is a branch, change it to a // base and update the list element. // The base's left is the branches left. // The result is the base's right. val result = rcd.right+1 println("ack(${rcd.left}, ${rcd.right})=${rcd.right+1}") list.pop() val branch = list[0] if (branch is Record.Branch) { val record: IntRecord = Record.Base(branch.value, result) list[0] = record // Otherwise, we don't have a branch so we // are done and need to return the result // to the caller. } else return result // Otherwise, if the right side is zero, // subtract one from the left to add it // to the right. } else if (rcd.right == 0) { // Replace the record on the list with // the new one and display the debugging. val record: IntRecord = Record.Base(rcd.left-1, 1) list[0] = record println("ack(${rcd.left}, ${rcd.right})=ack(${rcd.left-1}, 1)") // Otherwise, replace the base with a new // one, the left as is and the right minus // one. When it eventually has a final // result, it is the right side of the // branch record, who's left side minus // one from the current value. The branch // is inserted to be processed later. } else { var record: IntRecord = Record.Base(rcd.left, rcd.right-1) list[0] = record record = Record.Branch(rcd.left-1, record) list.insert(1, record) println("ack(${rcd.left}, ${rcd.right})=ack(${rcd.left-1}, ack(${rcd.left}, ${rcd.right-1}))") } // if } // is // Should never get here, but is required by // the compiler for completeness. is Record.Branch -> break@done } // when } // while return 0 } // ack // Ackermann function recursive implementation with // debugging. Keep tract of our recursion nesting // level plus how many times we're called. fun A(l: Int, m: Int, n: Int): Int = // If the left integer is zero, the result to // return is the one more than right. Added // debugging to keep track of calls and maximum // nesting level. if (m == 0) { count++ if (l > maxLevel) maxLevel = l println("A($m, $n)=${n+1}") n+1 // Otherwise, if the right side is zero, subtract // one from the left to add it to the right then // recurse with those numbers. Plus debugging. } else if (n == 0) { count++ if (l > maxLevel) maxLevel = l println("A($m, $n)=A(${m-1}, 1)") A(l+1, m-1, 1) // Otherwise, recurse twice having the first with // the left as is and the right minus one. When // it eventually returns, it's value is the right // side of the second call and the left side // minus one. Plus debugging. } else { count++ if (l > maxLevel) maxLevel = l println("A($m, $n)=A(${m-1}, A($m, ${n-1}))") A(l+1, m-1, A(l+1, m, n-1)) } // if fun main(args: Array) { val first = rand(2, 3) val second = rand(2, 4) println("ack($first, $second) is ${ack(first, second)} after $loop loops.") println("A($first, $second) is ${A(0, first, second)} after $count calls nesting to $maxLevel recursions.") }

Ackermann mn