// Created for this challenge: // https://www.sololearn.com/post/230643 // Recursion Versus Loop // Pick one or more of the following choices // and solve with both recursion & loop. // Choices are: Ackermann Algorithm, // Factorial Algorithm, Fibonacci Numbers, // Hofstadter's Q-Sequence, Prime Number // List, Recamán's Sequence, plus any // suggestions you or others can think of. // Display ten values of each side by side. // If you hit SoloLearn's timeout, you can // solve less values or randomly pick the // set of algorithms to perform. But, you // must test to be sure what you picked // will complete. // Output should be formatted into columns // for each choice. Strings for the call or // cardinal count should be right justified // in their column. Integers for results // should be right justified in their // columns. // Ackermann Algorithm: // A(0, 1) 2 2 // A(1, 0) 2 2 // A(0, 2) 3 3 // A(1, 1) 3 3 // A(2, 0) 3 3 // A(0, 3) 4 4 // A(1, 2) 4 4 // A(0, 4) 5 5 // A(1, 3) 5 5 // A(2, 1) 5 5 // Factorial Algorithm: // F(0) 1 1 // F(1) 1 1 // F(2) 2 2 // F(3) 6 6 // F(4) 24 24 // F(5) 120 120 // F(6) 720 720 // F(7) 5040 5040 // F(8) 40320 40320 // F(9) 362880 362880 // Fibonacci Numbers: // F(0) 0 0 // F(1) 1 1 // F(2) 1 1 // F(3) 2 2 // F(4) 3 3 // F(5) 5 5 // F(6) 8 8 // F(7) 13 13 // F(8) 21 21 // F(9) 34 34 // Hofstadter's Q-Sequence: // Q(1) 1 1 // Q(2) 1 1 // Q(3) 2 2 // Q(4) 3 3 // Q(5) 3 3 // Q(6) 4 4 // Q(7) 5 5 // Q(8) 5 5 // Q(9) 6 6 // Q(10) 6 6 // Prime Number List: // 1st: 2 2 // 2nd: 3 3 // 3rd: 5 5 // 4th: 7 7 // 5th: 11 11 // 6th: 13 13 // 7th: 17 17 // 8th: 19 19 // 9th: 23 23 // 10th: 29 29 // Recaman's Sequence: // R(0): 0 0 // R(1): 1 1 // R(2): 3 3 // R(3): 6 6 // R(4): 2 2 // R(5): 7 7 // R(6): 13 13 // R(7): 20 20 // R(8): 12 12 // R(9): 21 21 // Sealed class to hold Ackermann postponed // calls, until we have the answer they // require. sealed class Ackermann { // Class when both arguments are integers. class Base(val m: T, val n: T): Ackermann() // Class when the second points to another // instance. class Branch(val value: T, val next: Ackermann): Ackermann() } // Record // Type alias to simplify the looks of the // type. typealias IntAckermann = Ackermann // Function to solve Ackermann Algorithm both // by recursion and loop. The algorithm is: // both m and n must be positive or zero // A(m, n) is: // n+1 when m is zero // A(m-1, 1) when n is zero // A(m-1, A(m, n-1)) fun ackermann() { // Map to hold our table of keys (function // arguments) and values (function results.) val map = mutableMapOf, List>() // Function to implement Ackermann by // recursion. fun recursive(m: Int, n: Int): Int = when { // When the answer is already known, // return it from our map. listOf(m, n) in map -> map[listOf(m, n)]!![0] // When m is zero, put n+1 into // our map and return it. m == 0 -> { map.put(listOf(m, n), listOf(n+1)) map[listOf(m, n)]!![0] } // m // When n is zero, recurse with // m-1 & 1, put it's return into // our map, and return that value. n == 0 -> { map.put(listOf(m, n), listOf(recursive(m-1, 1))) map[listOf(m, n)]!![0] } // n // Otherwise, recurse with m & n-1, // recurse with m-1 & the return // from our first recurse, put the // return from our second recurse // into our map, and return that // value. else -> { map.put(listOf(m, n), listOf(recursive(m-1, recursive(m, n-1)))) map[listOf(m, n)]!![0] } // else } // when // Function to implement Ackermann by // looping. fun loop(m: Int, n: 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 list = mutableListOf( Ackermann.Base(m, n)) while (true) { // Get the data to process and, if we // have a base record, process it. val rcd = list.getOrNull(0) if (rcd is Ackermann.Base) { // If the left integer is zero, the // result to return is the right+1. if (rcd.m == 0) { // Calculate the result. The base // element is done so toss it. // Default found to false. For // each key in our map, if the // key is the one we are looking // for, note we found it. All the // rest get their value updated // with this result. val result = rcd.n+1 list.removeAt(0) var found = false for (key in map.keys) { if (key == listOf(rcd.m, rcd.n)) found = true if (found) map[key] = listOf( map[key]!![0], result) } // for // Get the branch to update. If // there is a branch, store our // result into our map, change // the branch to a base, and // update the list element. The // base's left is the branches // left. The result is the base's // right. val branch = list.getOrNull(0) if (branch is Ackermann.Branch) { val record: IntAckermann = Ackermann.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.n == 0) { // Replace the record on the // list with the new one. val record: IntAckermann = Ackermann.Base(rcd.m-1, 1) list[0] = record // 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: IntAckermann = Ackermann.Base(rcd.m, rcd.n-1) list[0] = record record = Ackermann.Branch( rcd.m-1, record) list.add(1, record) } // if } // if } // while return 0 } // loop // Run both ways storing the first ten // keys and values. recursive(2, 1) loop(2, 1) // Display the results by accessing each // key. println("Ackermann Algorithm:") for (key in map.keys) { val (m, n) = key val list = map[key]!! println("%9s%2d%2d".format("A($m, $n)", list[0], list[1])) } // for println() } // ackermann // Function to solve Hofstadter-Conway both // by recursion and loop. The sequence is: // n must be positive // A(n) is: // 1 when n is one or two // A(A(n-1))+A(n-A(n-1)) fun conway() { // Map to hold our table of keys (function // arguments) and values (function results.) val map = mutableMapOf>() // Function to implement Hofstadter-Conway // by recursion. fun recursive(n: Int): Int = // If we already have n in the map, // return it, if (n in map) map[n]!![0] // Otherwise, if n is one or two, put // one into our map and return it. else if (n in 1..2) { map.put(n, listOf(1)) map[n]!![0] // Otherwise, recurse with n-1 & // recurse with that result for // the first half. Recursive with // n-1 subtract that result from // n to recurse with that value // for the second half. Add // both halves together, put it // into our map for n, and return // it. } else { map.put(n, listOf(recursive( recursive(n-1))+recursive( n-recursive(n-1)))) map[n]!![0] } // if // Function to implement Hofstadter-Conway // by looping. fun loop(n: Int): Int { // Default our result to zero. For each // Hofstadter-Conway from one to n, // calculate it and update our map with // it. var result = 1 for (value in 1..n) { result = if (value <= 2) 1 else map[map[value-1]!![1]]!![1]+ map[value-map[value-1]!![1] ]!![1] map[value] = listOf(map[value]!![0], result) } // for return result } // loop // Run both ways storing the first ten // keys and values. recursive(10) loop(10) // Display the results by accessing each // key. println("Hofstadter-Conway:") for (key in map.keys) { val list = map[key]!! println("%6s%2d%2d".format("A($key)", list[0], list[1])) } // for println() } // conway // Function to solve Factorial Algorithm both // by recursion and loop. The algorithm is: // n must be positive or zero // F(n) is: // 1 when n is zero // n*F(n-1) fun factorial() { // Map to hold our table of keys (function // arguments) and values (function results.) val map = mutableMapOf>() // Function to implement Factorial by // recursion. fun recursive(n: Int): Int = // If n is zero, put one into our map // and return it. if (n == 0) { map.put(n, listOf(1)) map[n]!![0] // Otherwise, recurse with n-1, // multiply n by the recurse return, // put that result into our map, and // return it. } else { map.put(n, listOf(n*recursive(n-1))) map[n]!![0] } // if // Function to implement Factorial by // looping. fun loop(n: Int): Int { // Default our result to one. For each // factorial from zero to n, calculate // it and update our map with it. var result = 1 for (value in 0..n) { result *= if (value == 0) 1 else value map[value] = listOf(map[value]!![0], result) } // for return result } // loop // Run both ways storing the first ten // keys and values. recursive(9) loop(9) // Display the results by accessing each // key. println("Factorial Algorithm:") for (key in map.keys) { val list = map[key]!! println("%6s%7d%7d".format("F($key)", list[0], list[1])) } // for println() } // factorial // Function to solve Fibonacci Numbers both // by recursion and loop. The algorithm is: // n must be positive or zero // F(n) is: // n when n is zero or one // F(n-1)+F(n-2) fun fibonacci() { // Map to hold our table of keys (function // arguments) and values (function results.) val map = mutableMapOf>() // Function to implement Fibonacci Numbers // by recursion. fun recursive(n: Int): Int = // If we already have n in the map, // return it, if (n in map) map[n]!![0] // else if we want either of the // first two values, they are fixed // so put it into our map and return // it. else if (n <= 1) { map.put(n, listOf(n)) map[n]!![0] // Otherwise, calculate our result by // recursing twice with n-2 & n-1 and // add them together. Put it in our // map and return it. } else { val result = recursive(n-2)+ recursive(n-1) map[n] = listOf(result) map[n]!![0] } // if // Function to implement Fibonacci Numbers // by looping. fun loop(n: Int): Int { // Default our result to zero. For each // fibonacci from zero to n, calculate // it and update our map with it. var result = 1 for (value in 0..n) { result = if (value <= 1) value else map[value-2]!![1]+map[value-1]!![1] map[value] = listOf(map[value]!![0], result) } // for return result } // loop // Run both ways storing the first ten // keys and values. recursive(9) loop(9) // Display the results by accessing each // key. println("Fibonacci Numbers:") for (key in map.keys.sorted()) { val list = map[key]!! println("%6s%3d%3d".format("F($key)", list[0], list[1])) } // for println() } // fibonacci // Function to solve Hofstadter's Q-Sequence // both by recursion and loop. The sequence // is: // n must be positive // Q(n) is: // 1 when n is one or two // Q(n-Q(n-1))+Q(n-Q(n-2)) fun hofstadter() { // Map to hold our table of keys (function // arguments) and values (function results.) val map = mutableMapOf>() // Function to implement Hofstadter's // Q-Sequence by recursion. fun recursive(n: Int): Int = // If we already have n in the map, // return it, if (n in map) map[n]!![0] // else if we want either of the // first two values, they are fixed // so put it into our map and return // it. else if (n <= 2) { map.put(n, listOf(1)) map[n]!![0] // Otherwise, calculate our result by // recursing twice with n-2 & n-1 and // add them together. Put it in our // map and return it. } else { val result = recursive(n- recursive(n-1))+recursive(n- recursive(n-2)) map[n] = listOf(result) map[n]!![0] } // if // Function to implement Hofstadter's // Q-Sequence by looping. fun loop(n: Int): Int { // Default our result to zero. For each // hofstadter from one to n, calculate // it and update our map with it. var result = 1 for (value in 1..n) { result = if (value <= 2) 1 else map[value-map[value-1 ]!![1]]!![1]+map[value- map[value-2]!![1]]!![1] map[value] = listOf(map[value]!![0], result) } // for return result } // loop // Run both ways storing the first ten // keys and values. recursive(10) loop(10) // Display the results by accessing each // key. println("Hofstadter's Q-Sequence:") for (key in map.keys.sorted()) { val list = map[key]!! println("%7s%2d%2d".format("Q($key)", list[0], list[1])) } // for println() } // hofstadter // Function to solve Prime Number List both // by recursion and loop. The primes are: // 2, 3, 5, 7, 11, ... fun prime() { // Map to hold our table of keys (function // arguments) and values (function results.) val map = mutableMapOf>() // Function to implement Prime Number List // by recursion. fun recursive(n: Int): Int = // If we want the first prime, it is // two so put it into our map and // return it. if (n == 1) { map.put(n, listOf(2)) map[n]!![0] // Otherwise, get the previous prime, // note we have not found ours, and // loop until we do. } else { var last = recursive(n-1) var found = false while (!found) { // Increment to the next possible, // pretend it is prime, for // each previous prime see if // can prove our possible can't // be. last += if (last == 2) 1 else 2 found = true for (value in map.values) if (last%value[0] == 0) { found = false break } // if } // while // Put our prime into the map and // return it. map.put(n, listOf(last)) map[n]!![0] } // if // Function to implement Prime Number List // by looping. fun loop(n: Int): Int { // Default our result to one so it can // be incremented to two in the loop. // For the first ten primes, find one. var result = 1 var count = 1 while (count <= n) { // Increment our result to the next // possible by one for two and three // and by two to remain odd // afterwards. result += if (result <= 2) 1 else 2 // Default to having found a prime // and, for all primes found so far, // see if our result is divisible // by the prime. If so, it can not // be a prime so note that and abort // our check. var found = true for (value in map.values) if (value.size == 2 && result%value[1] == 0) { found = false break } // if // If found is still true, we got our // next one so add it to the map and // increment to hunt for our nect one. if (found) { map[count] = listOf(map[count]!![0], result) count++ } // if } // while return result } // loop // Function to generate a cardinal display // string for a number. fun cardinal(n: Int) = when (n) { 1 -> "${n}st" 2 -> "${n}nd" 3 -> "${n}rd" else -> "${n}th" } // when // Run both ways storing the first ten // keys and values. recursive(10) loop(10) // Display the results by accessing each // key. println("Prime Number List:") for (key in map.keys) { val list = map[key]!! println("%7s%3d%3d".format( "${cardinal(key)}:", list[0], list[1])) } // for println() } // prime // Function to solve Recamán's Sequence both // by recursion and loop. The sequence is: // n must be positive or zero // A(n) is: // n when n is zero // A(n-1)-n when n is positive and it's // result is not already in sequence // A(n-1)+n fun recaman() { // Map to hold our table of keys (function // arguments) and values (function results.) val map = mutableMapOf>() // Function to implement Prime Number List // by recursion. fun recursive(n: Int): Int = // If n is zero, put it in the map // and return it. if (n == 0) { map.put(n, listOf(n)) map[n]!![0] // Otherwise, recurse to get n-1, // subtract n from the result, and // if it is negative or exists in the // sequence, adjust the result by // adding 2n. In either case, put the // result in the map and return it. } else { var result = recursive(n-1)-n if (result < 0 || listOf(result) in map.values) result += 2*n map.put(n, listOf(result)) map[n]!![0] } // if // Function to implement Prime Number List // by looping. fun loop(n: Int): Int { // Default our sequence to empty and // our result to zero. For zero to n, // if our n is zero, so is our result, // else our result is previous value // minus our sequence position. If // that result is negative or already // used in the sequence, our result is // previous value plus our sequence // position. Store the result in our // sequence and our map before // continuing our next loop. val sequence = MutableList(0) { 0 } var result = 0 for (count in 0..n) { if (count == 0) result = 0 else result = sequence[count-1]-count if (result < 0 || result in sequence) result = sequence[count-1]+count sequence.add(result) map[count] = listOf(map[count]!![0], result) } // for return result } // loop // Run both ways storing the first ten // keys and values. recursive(9) loop(9) // Display the results by accessing each // key. println("Recaman's Sequence:") for (key in map.keys) { val list = map[key]!! println("%7s%3d%3d".format( "R($key):", list[0], list[1])) } // for println() } // recaman // Main function for the challenge. Process // each of the existing choices. fun main(args: Array) { ackermann() conway() factorial() fibonacci() hofstadter() prime() recaman() } // main

recursive ch