标签: tail-recursion

嘿伙计们,我正在尝试使用函数式编程(特别是使用F#),并且在构建尾递归函数时我遇到了问题.我很好地将基本递归(函数基本上每次调用一次调用自身)转换为尾递归,但我现在有一个稍微复杂的情况.

在我的例子中,该函数必须接受一个列表作为参数.调用该函数时,我必须从列表中删除第一个元素,然后使用列表的其余部分重复.然后我需要将我以某种方式删除的第一个元素应用于递归的结果.接下来,我删除第二个元素并执行相同的操作(注意:当我说"删除seond元素"时,即来自原始列表,因此在递归时传递的列表也包括第一个元素).我对列表的第三,第四等元素也这样做.

有没有办法将上述情况转换为尾递归函数？也许嵌套的尾递归函数??? 谢谢你的任何答案.

好的,这是我的基本代码.这个特定的一个是置换生成器(我不太关心置换部分,但是 - 这是我想关注的递归):

let permutationsOther str =
  match str with
  | value :: [] ->
    [[value]]
  | _ ->
    let list = (List.map (fun a -> // This applies the remove part for every element a
      let lst = (List.filter (fun b -> b <> a) str) // This part removes element a from the list
      let permutedLst = permutations lst // recursive call
      consToAll a permutedLst // constToAll this is my own function which performs …

可以使用Lwt.return作为递归函数的最终调用吗？

我有一个编译正常但功能不正常的函数,它看起来像f下面的函数.请假设g在此示例中提供的任何功能都没有问题,我基本上只是试图找出是否可以使用以下形式的函数,或者是否有更好/更简单(和Lwt兼容)的方式做以下事情:

 let rec f (x : string list) (g : string -> unit Lwt.t) =
   match List.length x with
   | 0 -> Lwt.return ()
   | _ -> g (List.hd x) >>= fun () -> f (List.tl x) g
 ;;
 val f : string list -> (string -> unit Lwt.t) -> unit Lwt.t = <fun>  

我很确定我做错了.但是我使用的实际功能比这个例子复杂得多,所以我很难调试它.

我有一个python方法,可以不时执行一些任务.我发现最简单的方法是写:

class MyClass:
    def a(self):
        #perform the task 
        time.sleep(time_to_sleep)
        self.a()

但是该方法应该运行很长时间,可能持续数月,这意味着它可以递归调用方法达10 ^ 4次.

这样做有风险吗？

我目前正在处理一个处理大量递归调用的副项目。我不是计算机科学家，所以我不确定如何优化我的代码。我知道递归函数的效率不是很高，而且我听说您经常可以用尾调用替换它，但我不确定如何去做。该函数接受三个数组：appendList、sequence 和 used。其他参数 base、length、index 和 last word 都是整数。

function Recursion(appendList, base, length, sequence, used, lastWord, index)
#Global variables:
global G_Seq_List
global G_Seq_Index

used = ones(UInt8, 1, base^length)
used[1] = 0

if index == base^length
    check = zeros(UInt8, base^length, 1)

    for i = 1 : base^length
        index = 1
        for j = 1 : length
            k = mod(i+j-1,base^length)
            index = index + base^(length - j)*sequence[k+1] 
        end

        check[index] = check[index] + 1

        if check[index] != 1 
            return
        end
    end

    G_Seq_List[G_Seq_Index,:] = sequence[:] …

所以我看到的尾递归的常见例子之一是：

function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return x * factorial(x-1); // (A)
    }
}

它针对尾调用进行了优化：

function factorial(n) {
    return facRec(n, 1);
}
function facRec(x, acc) {
    if (x <= 1) {
        return acc;
    } else {
        return facRec(x-1, x*acc); // (A)
    }
}

我明白了。但我的问题是：为什么*在这种情况下不是可以优化的功能？我不能将顶部重写为

function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return multiply(x, factorial(x-1)); // (A)
    }
}

我知道这行不通。我认为这只是因为它不是真正的尾递归调用？不过，这仍然是尾部优化吗？

如果我将以下递归深度优先搜索函数的第一行替换为在 foreach 块中注释掉的行，它将无法编译为尾递归函数（由于 @tailrec 注释），即使递归仍然显然是函数的最后一个动作。这种行为是否有正当理由？

@tailrec def searchNodes(nodes: List[Node], visitedNodes: List[Node], end: String, currentLevel: Int) : Int = {
    if (nodes.exists(n => n.id == end)) return currentLevel
    val newVisitedNodes = visitedNodes ::: nodes
    var nextNodes = List[Node]()
    nodes.foreach(n => {

        /*
        if (n.id == end){
            return currentLevel
        } 
        */
        nextNodes = nextNodes ::: n.addAdjacentNodes(visitedNodes)
    })
    if (nextNodes.size == 0) return -1
    return searchNodes(nextNodes, newVisitedNodes, end, currentLevel + 1)
}

我正在尝试用 Java 编写一个递归方法来查找 2 的倍数的基数 2 日志。

我已经使用这种递归方法成功计算了日志。

import java.util.*;

class temp
{
    static int log(int number)
    {
        if(number==1)
            return 0;
        return log(number/2)+1;
    }   
    public static void main(String s[])
    {
        Scanner input=new Scanner(System.in);
        System.out.println("Enter Multiple of 2:");
        System.out.println("Log is:"+log(input.nextInt())); //calling log with return value of nextInt()
    }
}   

我搁浅的地方是尝试使用不同的方法来实现相同的程序，在这种方法中，我在递归调用中从 2 开始乘以直到它等于给定的数字。这是我尝试过的：

class logarithmrecursion
    {
        static int step=1;
        static int log(int number)
        {
            final int temp=number;
            if(number>=temp && step!=1)
                return 0;
            step++;
            return log(number*2)+1;
            
        }
    }

在第一次调用期间，number 等于 temp，所以我使用了一个步进变量来防止终止条件的执行。如果我在递归调用中不使用“number”变量，我就没有办法累积前一个乘积但 number 变量已经等于 …

在为MIT/GNU Scheme (rel 9.2 ) 中的odd和even函数开发经典练习代码时，我遇到了一个问题，即我的代码不会因大整数值而终止。首先，我测试了以下代码，它处理正值和负值：

(define error-message-number "Error. x must be a number")

(define odd?
  (lambda (x)
    (cond 
      ((not (integer? x)) error-message-number)
      ((= x 0) #f)
      ((< x 0) (even? (+ x 1))) ;for negatives
      (else (even? (- x 1)))))) ;if number n is odd then n - 1 is even 

(define even?
  (lambda (x)
    (cond 
      ((not (integer? x)) error-message-number)
      ((= x 0) #t)
      ((< x 0) (odd? (+ x 1))) ;for negatives
      (else …