标签: tail-recursion

有人知道一个算法来对尾部进行简单的递归吗？更具体地说,您将如何将算法应用于以下代码？

namespace Testing
{
    class Program
    {
        static void Main(string[] args)
        {
           Console.WriteLine(match("?**", "aaa"));
           Console.WriteLine(match("*#*?", "aa1$a1a1"));
           Console.WriteLine(match("*#*", "aa11"));
           Console.WriteLine(match("??*", "0110"));
           Console.WriteLine(match("", "abc"));
           Console.WriteLine(match("???", ""));
           Console.ReadLine();

        }


        public static bool match(string p, string s)
        {
            if (p.Length == 0)
                return true;
            if (p.Length > s.Length)
                return false;

            bool firstLetterMatches = false;
            char nextCharInStr = s[0];
            switch (p[0])
            {
                case '*':
                    firstLetterMatches = 'a'<= nextCharInStr && nextCharInStr <= 'z';
                    break;

                case '#':
                    firstLetterMatches = '0'<= nextCharInStr && nextCharInStr <= '9';
                    break;

                case …

这是我的功能:

    //Data Structures :
    abstract class HuffmanTree
  case class Node(left: HuffmanTree, right: HuffmanTree, chars: List[Char], weight: Int) extends HuffmanTree
  case class Leaf(char: Char, weight: Int) extends HuffmanTree


  def find_char(tree: HuffmanTree, x: Char, accu: List[Int]): (Boolean, List[Int]) = {
    tree match {
      case Leaf(c, _) => ((x == c),accu)
      case Node(left, right, ll, _) =>
      (find_char(left,  x,  accu ::: List(0))._1 || find_char(right, x,  accu :::List(1))._1, accu);
    }
  }

该函数采用霍夫曼树,字符和累加器.该函数的目的是搜索霍夫曼树中的字符并对其进行编码.所以我遍历树,当我向左移动时,我向累加器添加0,当我向右移动时,我向累加器添加1.

我想知道这个函数是否是尾递归的？

我还有另一个问题.当我到达a时Leaf,返回的累加器始终为空.有人能解释我为什么会遇到这个问题吗？

作为进入合并排序的第一次尝试,我生成了以下代码,这些代码适用于字符串,因为它们比列表更容易处理.

class Program
{
    static int iterations = 0;
    static void Main(string[] args)
    {            
        string test = "zvutsrqponmlihgfedcba";
        test = MergeSort(test);
        // test is sorted after 41 iterations
    }

    static string MergeSort(string input)
    {
        iterations++;
        if (input.Length < 2)
            return input;
        int pivot = 0;
        foreach (char c in input)
            pivot += c;
        pivot /= input.Length;
        string left = "";
        string right = "";
        foreach (char c in input)            
            if (c <= (char)pivot)
                left += c;
            else
                right += c; …

我希望这个问题不是一个骗局.似乎大多数问题在一个语句中引用多个递归调用,即:return func(n - 1) * func(n - 2).我的问题涉及if/else语句中的多个递归调用.这就是我所拥有的(来自项目Euler问题):

def multOfThreeAndFive(n: Double): Double = {
  def loop(next: Double, acc: Double): Double = {
    if (next < 0) acc
    else if (next % 3 == 0 || next % 5 == 0) loop(next - 1, acc + next)
    else loop(next - 1, acc)
  }
  loop(n - 1, 0)
}

我的问题是,因为我正在进行两个单独的递归调用,一个在内部else if,另一个在最后一个内部else,这仍然被认为是尾递归的吗？

请考虑这段代码.

(loop [k from res '()]
    (if (< (count res) n)
      (recur (next-num k)  (conj res (next-num k)))
      (sort res)))

现在,假设函数(next-num k)执行了一些昂贵的计算.我们不能两次打电话.替代方案是什么？我是Clojure的新手,并不知道很多基本功能.但我相信一定有办法.

两个功能:

def eat(): Unit = sleep()
def sleep(): Unit = eat()

它们都是递归函数,因为它们在体内(间接地)称自己为对,对吧？

但它们是尾递归函数吗？

我看到包含一个接收块的函数被递归调用,似乎不是在elixir示例代码中的所有位置的尾部位置.例如:

defmodule A do
  def loop do
    receive do
      :ping ->
         IO.puts "Received :ping"
         loop # <- Tail position?
      :pong ->
         IO.puts "Received :pong"
         loop # <- Also Tail position?
      after
        5000 ->
          loop # <- Also Tail position?
     end
     loop # <- Also Tail position?
  end
end

是否会收到一个特殊的构造,在所有匹配块的末尾优化尾部位置？如果接收块有after块,它是否适用？如果函数中的接收块之后有代码怎么办？

我想做一个BigInteger的阶乘（在Kotlin中）。使用尾部递归时，当我尝试执行9000时会出现StackOverFlow错误！。使用非递归函数，我可以做到这一点……但是我很好奇如何避免这种错误。

这是我的代码：

import java.math.BigInteger

fun tail_recursion_factorial(n: BigInteger, factorialOfN: BigInteger = BigInteger.valueOf(2)): BigInteger {
   return when(n){
        BigInteger.ONE ->  BigInteger.ONE
        BigInteger.valueOf(2) ->  factorialOfN
        else -> tail_recursion_factorial(n.minus(BigInteger.ONE), n.times(factorialOfN))
    }
}
fun non_recursive_factorial(n: BigInteger): BigInteger{
    var i: BigInteger = BigInteger.ONE
    var factorial: BigInteger = BigInteger.ONE
    while (i<=n){
        factorial = factorial.times(i)
        i = i.plus(BigInteger.ONE)
    }
    return factorial
}
fun main(args: Array<String>){
    print("n == ")
    var n = readLine()!!
    //recursive
    //println("$n! is ${tail_recursion_factorial(BigInteger(n))}")
    //non-recursive
    println("$n! is ${non_recursive_factorial(BigInteger(n))}")
}

I have implemented Sphere function (takes a List of elements, squares every element and returns sum) in Scala. I want to convert this function to tail recursive. My code is here

def Sphere(list: List[Double]): Double = {
  val power = list.map(math.pow(_, 2))
  power.reduce(_+_)
}

I have the following function in scala:

def is_in[T](e: T, as: List[T]) : Boolean = as match
{
  case Nil => false;
  case x::xs => e == x || is_in(e, xs);
}

Now I want to make this function tail recursive. My idea is the following:

// tail recursive:

def is_in[T](e: T, as:List[T]) : Boolean =
{
  @tailrec
  def is_in_tailrec[T](e: T, as:List[T], acc: Boolean) : Boolean =
  {
    as match
    {
      case Nil => acc;
      case x::xs => is_in_tailrec(... here …