java中递归算法是什么怎么算的

一、递归算法基本思路：

Java递归算法是基于Java语言实现的递归算法。递归算法是一种直接或者间接调用自身函数或者方法的算法。递归算法实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法表示问题的解。递归往往能给我们带来非常简洁非常直观的代码形式，从而使我们的编码大大简化，然而递归的思维确实跟我们的常规思维相逆的，通常都是从上而下的思维问题，而递归趋势从下往上的进行思维。

二、递归算法解决问题的特点：

1递归就是方法里调用自身。

2在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

3递归算法代码显得很简洁，但递归算法解题的运行效率较低。所以不提倡用递归设计程序。

4在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

5在做递归算法的时候，一定把握出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口就是一个条件，当满足了这个条件的时候我们就不再递归了。

三、代码示例：

public class Factorial {

    //this is a recursive function

    int fact(int n){

        if (n==1) return 1;

        return fact(n-1)n;

    }

     

}     public class TestFactorial {

 

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        Factorial factorial=new Factorial();

        Systemoutprintln("factorial(5)="+factorialfact(5));

    }

}

代码执行流程图如下：

此程序中n=5就是程序的出口。

​递归是指函数或过程或子程序在运行过程序中直接或间接调用自身而产生的重入现象。

在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用的对象已知。

使用递归解决问题，思路清晰，代码少。但是在主流高级语言中（使用递归算法要耗用更多的栈空间，所以在堆栈尺寸受限制时，应避免采用。所有的递归算法都可以改写成与之等价的非递归算法。

〖问题描述〗

在一个8×8的棋盘里放置8个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。

〖问题分析〗(聿怀中学吕思博)

这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：

1、冲突。包括行、列、两条对角线：

（1）列：规定每一列放一个皇后，不会造成列上的冲突；

（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；

（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。

2、数据结构。

（1）解数组A。A[I]表示第I个皇后放置的列；范围：18

（2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：18

（3）对角线冲突标记数组C、D。

C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-77

D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：216

〖算法流程〗

1、数据初始化。

2、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于0（未被占领）:

如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；

如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。

3、当n>;8时，便一一打印出结果。

〖优点〗逐一测试标准答案，不会有漏网之鱼。

〖参考程序〗queenpas

----------------------------------------------------------------------------

programtt;

vara:array[18]ofinteger;

b,c,d:array[-716]ofinteger;

t,i,j,k:integer;

procedureprint;

begin

t:=t+1;

write(t,'');

fork:=1to8dowrite(a[k],'');

writeln;

end;

proceduretry(i:integer);

varj:integer;

begin

forj:=1to8do

if(b[j]=0)and(c[i+j]=0)and(d[i-j]=0)then

begin

a:=j;

b[j]:=1;

c[i+j]:=1;

d[i-j]:=1;

ifi<8thentry(i+1)

elseprint;

b[j]:=0;

c[i+j]:=0;

d[i-j]:=0;

end;

end;

begin

fork:=-7to16do

begin

b[k]:=0;

c[k]:=0;

d[k]:=0;

end;

try(1);

end

==========================================

这是N皇后问题，看看吧：

在NN的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。

const max=8;

var i,j:integer;

a:array[1max] of 0max; //放皇后数组

b:array[22max] of boolean; // ‘/’对角线标志数组}

c:array[-(max-1)max-1] of boolean;// ‘\’对角线标志数组}

col:array[1max] of boolean; //列标志数组}

total:integer; //统计总数}

procedure output; //这里是输出过程

var i:integer;

begin

write('No':4,'[',total+1:2,']');

for i:=1 to max do write(a[i]:3);write(' ');

if (total+1) mod 2 =0 then writeln; inc(total);

end;

function ok(i,dep:integer):boolean; //判断第dep行第i列可放否？

begin

ok:=false;

if ( b[i+dep]=true) and ( c[dep-i]=true) and

(col[i]=true) then ok:=true

end;

procedure try(dep:integer);

var i,j:integer;

begin

for i:=1 to max do //每一行均有max种放法，对吧？xixi~~~~

if ok(i,dep) then begin

a[dep]:=i;

b[i+dep]:=false; // ‘/’对角线已放标志

c[dep-i]:=false; // ‘\’对角线已放标志

col[i]:=false; // 列已放标志

if dep=max then output

else try(dep+1); // 递归下一层

a[dep]:=0; //取走皇后,回溯

b[i+dep]:=true; //恢复标志数组

c[dep-i]:=true;

col[i]:=true;

end;

end;

begin

for i:=1 to max do begin a[i]:=0;col[i]:=true;end;

for i:=2 to 2max do b[i]:=true;

for i:=-(max-1) to max-1 do c[i]:=true;

total:=0;

try(1);

writeln('total:',total);

end

方案一（深度优先搜索）：

var ans:array[18] of integer; //记录答案的数组，记录在第1到第8行皇后所在的列；

lie:array[18] of boolean; //记录1到8中某列是否已经被另一个皇后占用；

zx:array[216] of boolean; //正斜线（左下向右上）数组，该斜线特点为：斜线上每一格的行加列的和一定，和为从2到16 9士捎到16来表示这15条正斜线，于是该数组记录了2到16中某条正斜线是否已经被另一个皇后占用；

fx:array[-77] of boolean; //反斜线（左上向右下）数组，该斜线特点为：斜线上每一格的行减列的差一定，差为从-7到7 9士捎7到7来表示这15条正斜线，于是该数组记录了2到16中某条正斜线是否已经被另一个皇后占用；

temp:integer; //记录总方案数；

procedure print; //该子程序负责输出方案；

var i:integer;

begin

write('zuobiao');

for i:=1 to 8 do

write(' (',i,',',ans[i],')'); //i代表行，ans[i]代表列；

writeln;

end;

procedure search(i:integer); //i为行，即表示放到了第几个皇后（因为一行有且只有1个皇后);

var j:integer;

begin

if i=9 then //递归出口，当搜索到第九行时，便得到一种方案；

begin

print; //输出该方案；

inc(temp); //每输出（得到）一种方案，总方案数变加1；

exit; //退出；

end;

for j:=1 to 8 do if not lie[j] and not zx[i+j] and not fx[i-j] then //当前位置，该列，正斜线，反斜线上均未被另一个皇后占用，即可以摆放一个皇后；

begin

lie[j]:=true; //设置标志，该行

zx[i+j]:=true; // 该正斜线

fx[i-j]:=true; // 该反斜线上已被皇后占用，不可再放皇后；

ans[i]:=j; //记录答案（第i行皇后所在列j）；

search(i+1); //实行下一层递归；

lie[j]:=false; //恢复标志（回溯）；

zx[i+j]:=false;

fx[i-j]:=false;

end;

end;

begin //主程序；

temp:=0; //给总方案数设初值为0;

fillchar(lie,sizeof(lie),0); //分别给列;

fillchar(zx,sizeof(zx),0); // 正斜线;

fillchar(fx,sizeof(fx),0); // 反斜线数组设初值为False;

search(1); //从第一行开始进行搜索；

writeln(temp); //再输出总方案数；

end

方案二（位运算加速）：

var

upperlim,sum:integer;

procedure test(row,ld,rd:integer);

var

pos,p:integer;

begin

if row<>upperlim then

begin

pos:=upperlim and not (row or ld or rd);

while pos<>0 do

begin

p:=pos and -pos;

pos:=pos-p;

test(row+p,(ld+p)shl 1,(rd+p)shr 1);

end;

end

else

inc(sum);

end;

begin

upperlim:=(1 shl 8)-1;

test(0,0,0);

writeln(sum);

end

设置一个三维数组，第一个下标是皇后的行坐标，第二个下标是皇后的列坐标，第三个下标是残卷号。相当于有N张叠在一起的88棋盘，每张棋盘只在复制前面棋盘及皇后后加放置一个皇后。直到放满8皇后后才是一张完整的8皇后图，称完卷。

递归，简单说是子程序自己调用自己。

例子：

版本 2

子程序 左右查找

参数 左边值, 整数型

参数 右边值, 整数型

参数 查找数组, , 数组

参数 ww, , 参考 可空 数组

局部变量 i, 整数型

局部变量 j, 整数型

局部变量 中间值, 整数型

如果真 (左边值 ≥ 右边值)

返回 ()

如果真结束

i ＝ 左边值

j ＝ 右边值

判断循环首 (j ≠ i)

判断循环首 (查找数组 [左边值] ≤ 查找数组 [j] 且 i ＜ j)

j ＝ j － 1

判断循环尾 ()

判断循环首 (查找数组 [左边值] ≥ 查找数组 [i] 且 i ＜ j)

i ＝ i ＋ 1

判断循环尾 ()

如果真 (i ＜ j)

中间值 ＝ 查找数组 [j]

查找数组 [j] ＝ 查找数组 [i]

查找数组 [i] ＝ 中间值

如果真结束

判断循环尾 ()

中间值 ＝ 查找数组 [左边值]

查找数组 [左边值] ＝ 查找数组 [i]

查找数组 [i] ＝ 中间值

左右查找 (左边值, i － 1, 查找数组, ) ' 继续处理左边的，这里是个递归的过程

左右查找 (i ＋ 1, 右边值, 查找数组, ) ' 继续处理右边的，这里是个递归的过程

ww ＝ 查找数组

' 以上是快速排序的代码实现，核心所在是递归的过程。

Private Sub Command1_Click()

a = CInt(Text1Text)

b = CInt(Text2Text)

x = 0

gcd a, b, x

Label1Caption = "Gcd(" & a & "," & b & ")=" & x

End Sub

Private Sub Form_Load()

Label1Caption = ""

Text1Text = ""

Text2Text = ""

End Sub

Sub gcd(a, b, x)

If a Mod b = 0 Then

  x = b

Else

  gcd b, a Mod b, x

End If

End Sub

1、递归做为一种算法在程序设计语言中广泛使用，是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。

2、递归算法一般用于解决三类问题：

1）数据的定义是按递归定义的。（Fibonacci（斐波那契）的函数）

2）问题解法按递归算法实现。（回溯）

3）数据的结构形式是按递归定义的。（树的遍历，图的搜索）

以上就是关于java中递归算法是什么怎么算的全部的内容，包括:java中递归算法是什么怎么算的、递归的定义是什么、急求！！pascal n皇后问题 (递归） 带详细解析等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！