递归函数是一个自己调用的函数

它允许程序员用最少的代码编写高效的程序。

缺点是，如果编写不当，它们可能会导致无限循环和其他意外结果。

我将解释简单递归函数和尾部递归函数

为了编写简单的递归函数

首先要考虑的一点是你应该什么时候决定出来是if循环的第二个问题是，如果我们是自己的职能部门，我们应该做什么

从给定的示例中：

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

从上面的例子中

if(n <=1)
     return 1;

是何时退出循环的决定因素

else 
     return n * fact(n-1);

是否要进行实际处理

为了便于理解，让我逐一完成任务。

让我们看看如果我运行事实（4），内部会发生什么

替换n=4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

如果循环失败，则转到else循环因此它返回4*事实（3）

在堆栈内存中，我们有4*事实（3）替换n=3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

如果循环失败，则转到else循环

因此它返回3*事实（2）

记住我们称之为“4*事实”（3）``

事实（3）的输出=3*事实（2）

到目前为止，堆栈具有4*事实（3）=4*3*事实（2）

在堆栈内存中，我们有4*3*事实（2）替换n=2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

如果循环失败，则转到else循环

因此它返回2*事实（1）

记住我们称之为4*3*事实（2）

事实（2）的输出=2*事实（1）

到目前为止，堆栈具有4*3*事实（2）=4*3*2*事实（1）

在堆栈内存中，我们有4*3*2*事实（1）替换n=1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

如果循环为真

所以它返回1

记住我们称之为4*3*2*事实（1）

事实（1）的输出=1

到目前为止，堆栈具有4*3*2*事实（1）=4*3*2*1

最后，事实（4）的结果=4*3*2*1=24

尾部递归将是

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

替换n=4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

如果循环失败，则转到else循环因此它返回事实（3，4）

在堆栈内存中，我们有事实（3，4）替换n=3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

如果循环失败，则转到else循环

因此它返回事实（2，12）

在堆栈内存中，我们有事实（2，12）替换n=2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

如果循环失败，则转到else循环

因此它返回事实（1，24）

在堆栈内存中，我们有事实（1，24）替换n=1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

如果循环为真

因此它返回running_total

running_total=24的输出

最后，事实（4,1）的结果=24

这里有一个例子，而不是用文字来解释。这是阶乘函数的Scheme版本：

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

下面是一个阶乘的尾部递归版本：

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

在第一个版本中，您会注意到对事实的递归调用被馈送到乘法表达式中，因此在进行递归调用时，状态必须保存在堆栈中。在尾部递归版本中，没有其他S表达式等待递归调用的值，并且由于没有进一步的工作要做，状态不必保存在堆栈上。通常，Scheme尾部递归函数使用常数堆栈空间。

递归意味着函数调用自身。例如：

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

尾部递归是指结束函数的递归：

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

看，非终结函数（Scheme术语中的过程）做的最后一件事就是调用自己。另一个（更有用的）例子是：

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

在helper过程中，如果左边不是nil，最后一件事就是调用自己（AFTER cons something和cdr something）。这基本上就是如何映射列表的。

尾部递归有一个很大的优点，即解释器（或编译器，取决于语言和供应商）可以对其进行优化，并将其转换为相当于while循环的东西。事实上，在Scheme传统中，大多数“for”和“while”循环都是以尾部递归的方式完成的（据我所知，没有for和while）。

下面是一个使用尾部递归进行阶乘的常见Lisp示例。由于无堆栈的性质，人们可以进行疯狂的大型阶乘计算。。。

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

然后为了好玩，你可以尝试（格式化nil“~R”（！25））

这本摘自《Lua编程》一书的摘录展示了如何进行正确的尾部递归（在Lua中，但也应适用于Lisp）以及为什么它更好。

尾部调用[尾部递归]是一种goto-dressed作为呼叫。当函数调用另一个作为其最后一个行动，所以它没有其他事情可做。例如在以下代码中，对g的调用是尾调用：函数f（x）返回g（x）终止在f调用g之后，它没有其他内容在这种情况下，程序不需要返回调用函数时调用的函数末端。因此在尾呼之后，程序不需要保留任何有关调用函数的信息在堆栈中。。。因为正确的尾呼使用no堆栈空间一个程序可以生成。例如，我们可以使用任意数字作为自变量；它永远不会溢出堆栈：函数foo（n）如果n>0，则返回foo（n-1）end终止…正如我前面所说的，尾呼是有点后顾之忧。因此，一个非常有用的正确的尾部调用在Lua用于编程状态机。此类应用程序可以代表功能状态；更改状态是去（或打电话）一个特定的作用例如，让我们考虑一个简单的迷宫游戏。迷宫有几个房间，每个房间最多四个门：北、南、东和西在每个步骤中，用户输入移动方向。如果有门在该方向上，用户将相应的房间；否则程序打印警告。目标是从最初的房间到最后的房间房间该游戏是典型的状态机，其中当前房间是状态。我们可以用一个每个房间的功能。我们用尾巴从一个房间移动到另一个有四个房间的小迷宫可能看起来像这样：功能室1（）本地移动=io.read（）如果移动==“南”，则返回房间3（）elseif move==“east”然后返回room2（）否则打印（“无效移动”）返回房间1（）--呆在同一个房间终止终止功能室2（）本地移动=io.read（）如果move==“south”，则返回room4（）elseif move==“west”然后返回房间1（）否则打印（“无效移动”）返回室2（）终止终止功能室3（）本地移动=io.read（）如果move==“north”，则返回room1（）elseif move==“east”然后返回room4（）否则打印（“无效移动”）返回室3（）终止终止功能室4（）打印（“恭喜！”）终止

因此，当您进行如下递归调用时：

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

这不是尾部递归的，因为在进行递归调用之后，您仍然需要在该函数中做一些事情（添加1）。如果输入的数字很高，可能会导致堆栈溢出。

尾部递归函数是一个递归函数，其中递归调用是函数中最后执行的事情。

常规递归函数，我们有堆栈，每次调用递归函数中的递归函数时，都会向调用堆栈添加另一层。在正常递归中空间：O（n）尾递归使空间复杂性从

O(N)=>O(1)

尾部调用优化意味着可以从另一个函数调用函数，而不增加调用堆栈。我们应该在递归解中编写尾部递归。但某些语言实际上不支持其引擎中的尾部递归，该引擎将语言向下编译。自从ecma6以来，规范中就有了尾部递归。但编译js的引擎都没有实现尾部递归。你无法在js中实现O（1），因为编译器本身不知道如何实现这种尾部递归。截至2020年1月1日，Safari是唯一支持尾部呼叫优化的浏览器。Haskell和Java具有尾部递归优化

正则递归阶乘

function Factorial(x) {
  //Base case x<=1
  if (x <= 1) {
    return 1;
  } else {
    // x is waiting for the return value of Factorial(x-1)
    // the last thing we do is NOT applying the recursive call
    // after recursive call we still have to multiply.
    return x * Factorial(x - 1);
  }
}

我们的调用堆栈中有4个调用。

Factorial(4); // waiting in the memory for Factorial(3)
4 * Factorial(3); //  waiting in the memory for Factorial(2)
4 * (3 * Factorial(2)); //  waiting in the memory for Factorial(1)
4 * (3 * (2 * Factorial(1)));
4 * (3 * (2 * 1));

我们正在进行4次Factorial（）调用，空间为O（n）这可能会导致堆栈溢出

尾部递归因子

function tailFactorial(x, totalSoFar = 1) {
  //Base Case: x===0. In recursion there must be base case. Otherwise they will never stop
  if (x === 0) {
    return totalSoFar;
  } else {
    // there is nothing waiting for tailFactorial to complete. we are returning another instance of tailFactorial()
    // we are not doing any additional computaion with what we get back from this recursive call
    return tailFactorial(x - 1, totalSoFar * x);
  }
}

在进行递归调用后，我们不需要记住任何内容