perl 递归入门
2014-02-07 22:12:07 
阿炯
递归(英语：recursion)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言(如Perl)中习惯用递归来实现循环。
计算机科学家尼克劳斯·维尔特如此描述递归：递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此在计算机科学中，递归可以被用来描述无限步的运算，尽管描述运算的程序是有限的。
递归算法解决问题的特点：
(1)、递归就是在过程或函数里调用自身。
(2)、在使用递增归策略时，必须有一个明确的递归结束条件，即递归出口。
(3)、在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。
递归算法所体现的“重复”一般有三个要求：
一是每次调用在规模上都有所缩小(通常是减半)；
二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
下面就列出了Perl环境下使用递归算法来解决实际问题的情形。
阶乘(Factorial)
sub fact{
my $arg = shift;
if ($arg == 1){
return 1;
}
my $var = $arg * fact($arg - 1);
return $var;
}
print "Factorial of: ",;
chomp(my $in = <STDIN>);
die $in, " is not a valid number!" if (!($in =~ /^\d+$/));
print fact($in);
运算部分还可以将其简写为：
my $arg = shift;
return $arg == 1? 1: $arg*fact($arg-1);
return (($arg == 1) || ($arg == 0)) ? 1 : $arg * fact($arg - 1);
数列算法(斐波那契，Fibonacci数列)
盘点一些计算代码，计算到34的斐波那契数列大小：
Recursive definition of Fibonacci
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)
原始代码实现：
sub fibonacci {
my $n=shift;
return 0 if $n==0;
return 1 if $n==1;
return fibonacci($n-1)+fibonacci($n-2);
}
print fibonacci(34);
perl one-liner：
perl -Mbigint -E '@c = (0, 1);$c[$_] = $c[$_-1] + $c[$_-2] for (2..34);say $c[34]'
优化思路
方法1：使用内存用空间换时间的方式
Fix using Memoize
One fix that has already been proposed is to use the core library Memoize
use Memoize;
memoize('fibonacci');
方法2：用循环代替递归
Create a loop instead - avoid recursion
示例1：
use v5.20;
use bigint;
print fibonacci(34), "\n";
sub fibonacci {
my $number = shift;
my @fib = ( 0, 1 );
for ( $#fib + 1 .. $number ) {
$fib[$_] = $fib[ $_ - 1 ] + $fib[ $_ - 2 ];
}
return $fib[$number];
}
real:0m0.056s
user:0m0.051s
sys:0m0.004s
主函数也可以这样写：
sub fibonacci {
my $n = shift;
my ($a,$b,$i) = (0,1,1);#$i for count
for ($i; $i <= $n; $i++) {
($a,$b) = ($a+$b,$a);
}
return $a;
}
本例使用了优化方法2，效率很高了，或这样也行：
my ($a, $b) = (0, 1);
($a, $b) = ($b, $a + $b) for 1 .. 34;
print $a;
示例2：
use v5.20;
use bigint;
use Memoize;
memoize('fibonacci');
print fibonacci(34);
sub fibonacci {
my ($n) = @_;
$n < 2 ? $n : fibonacci($n-1) + fibonacci($n-2);
#$n < 3 ? 1 : fibonacci($n-1) + fibonacci($n-2);
}
real:0m0.018s
user:0m0.016s
sys:0m0.001s
如果注释掉内存加速那两行，执行时间如下：
real:0m7.233s
user:0m7.221s
sys:0m0.000s
示例3：
use v5.20;
use bigint;
use Memoize;
memoize('fibo');
sub fibo{
my $arg = shift;
#return 0 if($arg<=0);
if($arg<2){
return $arg;
}else{
return fibo($arg-2) + fibo($arg-1);
}
}
print fibo(34);
real:0m0.060s
user:0m0.050s
sys:0m0.009s
如果注释掉内存加速那两行，执行时间会比较长，等待了一会后ctrl+c了。这样写也可以：
sub fib {
my $n = shift;
#return 1 if ($n == 1 or $n == 2);
return 1 if ($n <= 2);
return (fib($n-1)+fib($n-2));# recursive calling
}
示例4：
use v5.20;
use bigint;
sub fib_memo {
my $num = shift;
state $memo = { 1 => 1, 2 => 1 };
return $memo->{ $num } //= fib_memo( $num - 1 ) + fib_memo( $num - 2 );
}
print fib_memo(34);
real:0m0.054s
user:0m0.049s
sys:0m0.004s
示例5：利用v5.28及其后可对state数组进行初始化
use v5.28;
sub next_fib{
state @numbs=(0,1);
push @numbs,$numbs[-2]+$numbs[-1];
return $numbs[-1];
}
say next_fib() for (1..34);
real 0m0.008s
在机械工业出版社的《Perl高级编程》一书中，7.1.4章节的“递归”小段(第199页)中的第一和第三示例，极具参考意义。
#ppp-fib1
use v5.20;
sub fibonacci1 {
my ($cnt,$aref)=@_;
$aref=[1,1] unless $aref;
if($cnt--) {
my $next=$aref->[-1]+$aref->[-2];
push @{$aref},$next;
return fibonacci1($cnt,$aref);
} else {
return wantarray?@{$aref}:$aref->[-1];
}
}
#calculate 10th element of Fibonacci sequence
say scalar(fibonacci1(10));
#as above but use start sequence starting 2,4
say scalar(fibonacci1(10,[2,4]));
#return all ten elements of Fibonacci sequence
#my @sequence=fibonacci1(10);
#say "Sequence: @sequence"
$,=" ";
say 'Sequence:',fibonacci1(10);
say scalar(fibonacci1(34,[1,1]));
#ppp-fib3
use v5.32;
use bignum;
sub fibonacci3 {
my ($cnt,$aref)=@_;
$aref=[1,1] unless $aref;
if($cnt--) {
my $next=$aref->[-1]+$aref->[-2];
push @{$aref},$next;
@_=($cnt,$aref);
goto &fibonacci3;
} else {
return wantarray?@{$aref}:$aref->[-1];
}
}
#calculate 1000th element of Fibonacci sequence
#my $a=fibonacci3(1000);
#printf "%u\n",$a;
printf "%U\n",scalar(fibonacci3(34));
say '-' x 32;
my $calrs=sprintf "%lu",scalar(fibonacci3(34));
say "$calrs";
ppp-fib3的效率就没有ppp-fib1高了，使用操作的time指令的测试结果：前者(ppp-fib3，49ms)的耗时是后者(ppp-fib1，2ms)的20多倍。
数的进制转换
下面将十进制数转为二进制。
sub binary {
my ($n) = @_;
return $n if $n == 0 || $n == 1;#####这个就是上面说的递归出口
my $k = int($n/2);
my $b = $n%2;
my $E = binary($k);###函数自身调用，每次函数的输出，也是它的输入
return $E.$b;
}
print binary(17);
将会输出：10001
遍历目录，找出目录下以及所有子目录中的文件名
use 5.010;
my $path = shift || '.';
traverse($path);
sub traverse {
my ($thing) = @_;
say $thing;
return if not -d $thing;
opendir my $dh, $thing or die;
while (my $sub = readdir $dh) {
next if $sub eq '.' or $sub eq '..';
traverse("$thing/$sub");
}
close $dh;
return;
}
$ perl fr3.pl ~/data/vm
/home/hto/data/vm
/home/hto/data/vm/disk
/home/hto/data/vm/disk/workst_hd0.vdi
/home/hto/data/vm/disk/pde_disk.vdi
/home/hto/data/vm/pfrouter
/home/hto/data/vm/pfrouter/pfrouter.vbox-prev
/home/hto/data/vm/pfrouter/pfrouter.vdi
/home/hto/data/vm/pfrouter/Logs
/home/hto/data/vm/pfrouter/Logs/VBox.log.3
/home/hto/data/vm/pfrouter/Logs/VBox.log.2
/home/hto/data/vm/pfrouter/Logs/VBox.log.1
/home/hto/data/vm/pfrouter/Logs/VBox.log
/home/hto/data/vm/pfrouter/pfrouter.vbox
关于各种编程语言间的算法性能对比的参考。
langs-performance
2017年的golang、python、php、c++、c、java、Nodejs性能对比
计算机科学家尼克劳斯·维尔特如此描述递归：递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此在计算机科学中，递归可以被用来描述无限步的运算，尽管描述运算的程序是有限的。
递归算法解决问题的特点：
(1)、递归就是在过程或函数里调用自身。
(2)、在使用递增归策略时，必须有一个明确的递归结束条件，即递归出口。
(3)、在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。
递归算法所体现的“重复”一般有三个要求：
一是每次调用在规模上都有所缩小(通常是减半)；
二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
下面就列出了Perl环境下使用递归算法来解决实际问题的情形。
阶乘(Factorial)
sub fact{
my $arg = shift;
if ($arg == 1){
return 1;
}
my $var = $arg * fact($arg - 1);
return $var;
}
print "Factorial of: ",;
chomp(my $in = <STDIN>);
die $in, " is not a valid number!" if (!($in =~ /^\d+$/));
print fact($in);
运算部分还可以将其简写为：
my $arg = shift;
return $arg == 1? 1: $arg*fact($arg-1);
return (($arg == 1) || ($arg == 0)) ? 1 : $arg * fact($arg - 1);
数列算法(斐波那契，Fibonacci数列)
盘点一些计算代码，计算到34的斐波那契数列大小：
Recursive definition of Fibonacci
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)
原始代码实现：
sub fibonacci {
my $n=shift;
return 0 if $n==0;
return 1 if $n==1;
return fibonacci($n-1)+fibonacci($n-2);
}
print fibonacci(34);
perl one-liner：
perl -Mbigint -E '@c = (0, 1);$c[$_] = $c[$_-1] + $c[$_-2] for (2..34);say $c[34]'
优化思路
方法1：使用内存用空间换时间的方式
Fix using Memoize
One fix that has already been proposed is to use the core library Memoize
use Memoize;
memoize('fibonacci');
方法2：用循环代替递归
Create a loop instead - avoid recursion
示例1：
use v5.20;
use bigint;
print fibonacci(34), "\n";
sub fibonacci {
my $number = shift;
my @fib = ( 0, 1 );
for ( $#fib + 1 .. $number ) {
$fib[$_] = $fib[ $_ - 1 ] + $fib[ $_ - 2 ];
}
return $fib[$number];
}
real:0m0.056s
user:0m0.051s
sys:0m0.004s
主函数也可以这样写：
sub fibonacci {
my $n = shift;
my ($a,$b,$i) = (0,1,1);#$i for count
for ($i; $i <= $n; $i++) {
($a,$b) = ($a+$b,$a);
}
return $a;
}
本例使用了优化方法2，效率很高了，或这样也行：
my ($a, $b) = (0, 1);
($a, $b) = ($b, $a + $b) for 1 .. 34;
print $a;
示例2：
use v5.20;
use bigint;
use Memoize;
memoize('fibonacci');
print fibonacci(34);
sub fibonacci {
my ($n) = @_;
$n < 2 ? $n : fibonacci($n-1) + fibonacci($n-2);
#$n < 3 ? 1 : fibonacci($n-1) + fibonacci($n-2);
}
real:0m0.018s
user:0m0.016s
sys:0m0.001s
如果注释掉内存加速那两行，执行时间如下：
real:0m7.233s
user:0m7.221s
sys:0m0.000s
示例3：
use v5.20;
use bigint;
use Memoize;
memoize('fibo');
sub fibo{
my $arg = shift;
#return 0 if($arg<=0);
if($arg<2){
return $arg;
}else{
return fibo($arg-2) + fibo($arg-1);
}
}
print fibo(34);
real:0m0.060s
user:0m0.050s
sys:0m0.009s
如果注释掉内存加速那两行，执行时间会比较长，等待了一会后ctrl+c了。这样写也可以：
sub fib {
my $n = shift;
#return 1 if ($n == 1 or $n == 2);
return 1 if ($n <= 2);
return (fib($n-1)+fib($n-2));# recursive calling
}
示例4：
use v5.20;
use bigint;
sub fib_memo {
my $num = shift;
state $memo = { 1 => 1, 2 => 1 };
return $memo->{ $num } //= fib_memo( $num - 1 ) + fib_memo( $num - 2 );
}
print fib_memo(34);
real:0m0.054s
user:0m0.049s
sys:0m0.004s
示例5：利用v5.28及其后可对state数组进行初始化
use v5.28;
sub next_fib{
state @numbs=(0,1);
push @numbs,$numbs[-2]+$numbs[-1];
return $numbs[-1];
}
say next_fib() for (1..34);
real 0m0.008s
在机械工业出版社的《Perl高级编程》一书中，7.1.4章节的“递归”小段(第199页)中的第一和第三示例，极具参考意义。
#ppp-fib1
use v5.20;
sub fibonacci1 {
my ($cnt,$aref)=@_;
$aref=[1,1] unless $aref;
if($cnt--) {
my $next=$aref->[-1]+$aref->[-2];
push @{$aref},$next;
return fibonacci1($cnt,$aref);
} else {
return wantarray?@{$aref}:$aref->[-1];
}
}
#calculate 10th element of Fibonacci sequence
say scalar(fibonacci1(10));
#as above but use start sequence starting 2,4
say scalar(fibonacci1(10,[2,4]));
#return all ten elements of Fibonacci sequence
#my @sequence=fibonacci1(10);
#say "Sequence: @sequence"
$,=" ";
say 'Sequence:',fibonacci1(10);
say scalar(fibonacci1(34,[1,1]));
#ppp-fib3
use v5.32;
use bignum;
sub fibonacci3 {
my ($cnt,$aref)=@_;
$aref=[1,1] unless $aref;
if($cnt--) {
my $next=$aref->[-1]+$aref->[-2];
push @{$aref},$next;
@_=($cnt,$aref);
goto &fibonacci3;
} else {
return wantarray?@{$aref}:$aref->[-1];
}
}
#calculate 1000th element of Fibonacci sequence
#my $a=fibonacci3(1000);
#printf "%u\n",$a;
printf "%U\n",scalar(fibonacci3(34));
say '-' x 32;
my $calrs=sprintf "%lu",scalar(fibonacci3(34));
say "$calrs";
ppp-fib3的效率就没有ppp-fib1高了，使用操作的time指令的测试结果：前者(ppp-fib3，49ms)的耗时是后者(ppp-fib1，2ms)的20多倍。
数的进制转换
下面将十进制数转为二进制。
sub binary {
my ($n) = @_;
return $n if $n == 0 || $n == 1;#####这个就是上面说的递归出口
my $k = int($n/2);
my $b = $n%2;
my $E = binary($k);###函数自身调用，每次函数的输出，也是它的输入
return $E.$b;
}
print binary(17);
将会输出：10001
遍历目录，找出目录下以及所有子目录中的文件名
use 5.010;
my $path = shift || '.';
traverse($path);
sub traverse {
my ($thing) = @_;
say $thing;
return if not -d $thing;
opendir my $dh, $thing or die;
while (my $sub = readdir $dh) {
next if $sub eq '.' or $sub eq '..';
traverse("$thing/$sub");
}
close $dh;
return;
}
$ perl fr3.pl ~/data/vm
/home/hto/data/vm
/home/hto/data/vm/disk
/home/hto/data/vm/disk/workst_hd0.vdi
/home/hto/data/vm/disk/pde_disk.vdi
/home/hto/data/vm/pfrouter
/home/hto/data/vm/pfrouter/pfrouter.vbox-prev
/home/hto/data/vm/pfrouter/pfrouter.vdi
/home/hto/data/vm/pfrouter/Logs
/home/hto/data/vm/pfrouter/Logs/VBox.log.3
/home/hto/data/vm/pfrouter/Logs/VBox.log.2
/home/hto/data/vm/pfrouter/Logs/VBox.log.1
/home/hto/data/vm/pfrouter/Logs/VBox.log
/home/hto/data/vm/pfrouter/pfrouter.vbox
关于各种编程语言间的算法性能对比的参考。
langs-performance
2017年的golang、python、php、c++、c、java、Nodejs性能对比