递归,常出现在声明式范式的语言中,用来实现过程迭代的语义;正如循环,常出现在命令式的语言中,用来实现数据迭代的语义。递归一般有两种:尾递归(tail recursion)与非尾部递归(non-tail recusion),后者因为需要保存大量的临时变量,一般不被采用。下面使用不同的语言写一个常见的例子,求阶乘。
1)使用Java求阶乘
// 非尾递归
public class Math {
public static int fac(int n) {
return n == 0 ? 1 : fac(n-1) * n;
}
public static void main(String[] args) {
System.out.println(fac(5));
}
}
// 尾递归
public class Math {
public static int fac(int result, int n) {
return n == 0 ? result : fac(result*n, n-1);
}
public static int fac(int n) {
return fac(1, n);
}
public static void main(String[] args) {
System.out.println(fac(5));
}
}
2)使用C/C++求阶乘
// 非尾递归(C)
#include <stdio.h>
#include <stdio.h>
int fac(int n) {
return n == 0 ? 1 : fac(n-1) * n;
}
int main(int argc, char*argv[]) {
int result = fac(3);
printf("The result is %d ", result);
return 0;
}
// 尾递归(C++)
#include <iostream>
using namespace std;
int fac(int result, int n) {
return n == 0 ? result : fac(result*n, n-1);
}
int fac(int n) {
return fac(1, n);
}
int main(int argc, char*argv[]) {
int result = fac(3);
cout << "The result is " << result;
return 0;
}
3)使用JavaScript求阶乘
// 非尾递归
// 这里提供了一些简单的谓词,以纯函数的风格表达递归
function div(a, b){ return a/b; }
function dec(x){ return x - 1; }
function equal(a, b){ return a==b; }
function fac(n){
return equal(n, 1) ? 1 : mul(n, fac(dec(n)));
}
document.write(fac(3));
// 尾递归(版本1)
// 在这里,通过JavaScript中arguments模拟重载不适用,
// 简单起见,也不再多写一个函数封装fac(result, n)来简化其参数个数。
// 因为后面有更简洁的表达方法,即采用闭包和匿名函数技术。
function fac(result, n) {
return n == 0 ? result : fac(result*n, n-1);
}
document.write(fac(1, 3));
//尾递归(版本2)
// 这里采用闭包技术,但内部函数为具名函数,因为递归时需要呼叫函数的名字。
function fac(n) {
return (function fac(result, n) {
return n == 0 ? result : fac(result*n, n-1);
})(1, n);
}
document.write(fac(5));
//尾递归(版本3)
// 这里采用闭包技术,内部函数之所以可以是匿名函数,是因为arguments.callee
// 即参数的被调用者的属性,可以引用匿名函数,在递归时可用来呼叫。
function fac(n) {
return (function(result, n) {
return n == 0 ? result : arguments.callee(result*n, n-1);
})(1, n);
}
document.write(fac(5));
4)使用Erlang求阶乘
// non-tail recursion
-module(math).
-export([fac/1]).
fac(1) -> 1;
fac(N) -> N * fac(N - 1)
// tail recursion
-module(math).
-export([fac/1]).
fac(N) -> fac(1, N).
fac(Result, 1) -> Result;
fac(Result, N) -> fac(N * Result, N - 1).
分享到:
相关推荐
这是QL中递归谓词的些示例:以下查询使谓词 getANumber() 列出0到100(含)之间的所有整数:递归(Recursion)递归谓词的例从0到100计数
C# 实现汉诺塔问题 递归+Recursion 本人收藏了3年的资源 现放出 都是总结了很多系统 软件项目实施过程中的经验的 慢慢积累的
本手册主要是了解计算机科学、程序设计和问题解决的基本概念;理解什么是“抽象”以及抽象在问题解决过程中的作用;...递归 Recursion 119 5.排序与搜索 .158 6.树和树算法 .191 7.图和图算法 .259
同样有趣的例子 吃完一个bowl of chips:for loop,知道多少薯片,然后从0开始吃到最后递归,吃一片,然后继续吃剩下的 N - 1 片,直到碗里
recursion math 快慢双指针 stack set 二分查找 scan DP,fibonacci recursion DP 中序遍历 recursion 递归 recursion DP recursion or math math math DP DP 递归?回溯+减支? dfs recursion map (归并排序) math ...
关于递归程序的设计思路 如何利用递归思想来解题 解题步骤
这是从《黑马程序员》中的数据结构上册拿到的资源,同时结合了本作者的理解与笔记
22. 括号生成参考博客1力扣上不错的解解法1:回溯+剪枝对于这种列出所有结果的题首先还是考虑用递归 Recursion 来解,由于字符串只有左括号和右括号两种
Julia 代码聚合 ... 递归Recursion c. 变换等价Equivalent Transformation 2. 如果知道什么其他好的开源Julia 代码,欢迎联系! If any other open-sourced Julia codes are known, it is welcomed to co
输入:任意的上下文无关文法。 输出:消除了左递归的等价文法。
递归运算示例,这是个简单案例,基于此可以设计出多定义域函数求值程序。
lru cache leetcode ...递归Recursion(Divide & Conquer,Backtrace) 搜索Search:深度优先搜索Depth first search,广度优先搜索Breadth first search 动态规划Dynamic Programming 二分查找Binary S
解法:对原文法消除左递归,根据消除左递归后的等价文法建立语法树,而后对此语法树 进行后根遍历,即可得到后缀式.
递归简单(几乎)就是一切。 该项目包含递归算法,它展示了递归的简单性和强大的潜力,以及一个算法可视化工具。 这个可视化应用程序有一个算法接口,可以插入新算法,并提供一个接口来可视化和参数化算法。可视化...
猜单词leetcode 通过 leetcode 学习数据结构与算法 数据结构 data structure 数组(栈 队列) 链表 树 图 堆 空间换时间 (哈希表) 1 数组 (栈 stack 和 队列 queue) 20.有效的括号.js ...递归 ...递归 recursion +
recursion递归的一个案列,一切为了积分,不知道是不是这样就可以得到积分,所以试试
Python语言使用函数递归思想绘制圣诞树,递归算法(recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题,因此它是...
用到的技术:axios、vuex、v-router、font-awesome、scss、promise、递归组件、原生js 具体过程: 1、整体布局(layout.vue),分左边菜单、导航和内容区。 2、安装预测要用到的scss、vuex、axios、font-awesome等...
#递归这是递归的两个基本示例。 ##因子这在数学中完成了同样的问题: 阶乘(n) = 阶乘(n * 阶乘(n - 1)) 阶乘(1)= 1 factorial(4) = 24因为factorial(4) = 4 * 3 * 2 * 1 function factorial(n) {if (n == 1) {...
这些笔记教会学生抽象地思考算法以及用于开发它们的关键算法技术。