递归的定义？何时使用递归？递归模型？递归执行过程？常见的递归思想的例题和实现？

我会带着你远行 2021-07-24 13:37 400阅读 0赞

# 递归 #

**递归定义：**  
递归是指函数的定义中又调用函数自身的方法。

**例题**  
求n（n为正整数）的阶乘

int fun(int n){ 
         if(n==1) { 
           return  0;
         }
          else { 
         return (fun( n-1)*n);
         }
    }

这里需要注意的是递归问题的求解过程一般都需要返回值，在递归问题中没有返回值，会导致语法错误。

**何时使用递归方法**  
**1.定义是递归的，例如求阶乘和斐波那契数列**  
**2.数据结构是递归的，如单链表**  
**3.求解问题的方法是递归的，如梵塔问题**

**递归模型**  
递归模型分为递归体和递归终结条件，两者缺一不可。

int fun(int n){ 
         if(n==1) { 
           return  0;
         }
          else { 
         return (fun( n-1)*n);
         }
    }

在这个简单的例子中，递归体就是 (fun(n-1)\*n)，终结条件是 if（n==1）.

**递归的执行过程**

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

**常见递归思想的例题**  
1.求n阶乘

int fun(int n){ 
         if(n==1) { 
           return  0;
         }
          else { 
         return (fun( n-1)*n);
         }
    }

1.  斐波那契数列

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

int Fit(int n){ 
         if(n==1||n==2) { 
           return  1;
         }else { 
         return (Fit( n-1)*Fit(n-2));
         }
    }

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

3.n皇后问题  
n皇后问题：将n个皇后摆放在N\*N的棋盘中，互相不可攻击，有多少种摆放方式，每种摆放方式具体是怎样的？八皇后问题的核心思想就是放置之前检查行列四个斜方位即可。

package NQueensDG;
     
    import java.util.Scanner;
     
    public class NQUEENSDIGUI { 
     
    
    	//下面是数据成员--------------------------------------------------
    	static int n;//皇后个数
    	static int []x;//当前解
    	static long sum;
    	
    	//成员定义结束----------------------------------------------------
    	
    	NQUEENSDIGUI(int nn){ 
    		n =nn;
    		sum =0;
    		x = new int [n+1];
    		for(int i=0;i <= n ;i++)x[i]=0;//初始化都为0
    		backtrack(1);
    	}
    	
    	private void backtrack(int t) { 
    		// TODO 自动生成的方法存根
    		if(t > n){ 
    			sum++;
    			print(x);
    		}
    		else
    			for(int i=1;i<=n;i++){ 
    				x[t]=i;
    				if(place(t))backtrack(t+1);//递归调用，循环求解
    			}
    	}
     
    	private void print(int[] x2) { 
    		System.out.println((x2.length-1)+"皇后的解为：");
    		for(int i=1;i<=n;i++){ 
    			System.out.print(" "+x2[i]);
    		}
    		System.out.println("");
    	}
     
    	private boolean place(int k) { 
    		for(int j=1;j < k;j++){ 
    			if((Math.abs(k-j) == Math.abs(x[j]-x[k]))||(x[j] == x[k]))return false;
    		}
    		return true;
    	}
     
    	public static void main(String[] args) { 
    		int s;
    		Scanner input = new Scanner(System.in);
    		s = input.nextInt();
    		NQUEENSDIGUI a = new NQUEENSDIGUI(s);
    		System.out.println("---------------------------------");
    		System.out.println("华丽的"+s+"皇后问题解");
    		System.out.println(s+"皇后一共有："+sum+"个解!");
    		input.close();
    	}
    }

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

4.Hanio问题