递归法：
1）定义：
递归就是自己调用自己。
2）另外：
能不用递归就不要用递归，因为递归其实就是系统为你压栈了，系统会把所有的东西都压栈（不管你用不用得到），所以造成了递归耗内存。可以用循环来代替递归，自己实现压栈，压入自己需要用到的东西就好。
3）如何计算递归的时间复杂度







4）例子：
（1）问题描述：

求全排列。

（2）基本思路：

就是第一层perm固定了第一个元素arr[0]，第二层固定了第二个元素arr[1]，以此类推，到最后一个的时候就输出数组。

（3）Java代码实现：
public class digui {

    public static  void main(String[] args) {
        int arr[]= {1,2,3,4};
        perm(arr,0,arr.length-1);//求得/打印出 数组arr从0到arr.length-1的全排列

    }
    
    public static void swap(int arr[],int x, int y) {
        int temp = arr[x];
        arr[x]=arr[y];
        arr[y]=temp;

    }

    public static void perm(int arr[],int begin ,int end) {
        if(end==begin) {
            for(int i =0;i<=end;i++) {
                System.out.print(arr[i]+" ");
            }
            System.out.println();//用来使得每个排列在不同的行上，过行作用
            return;
        }else {
            for(int j =begin;j<=end;j++) {
                swap(arr,begin,j);//更换第一个数的数值
                perm(arr,begin+1,end);//求得arr除了第一位数以后的全排列
                swap(arr,begin,j);//更换回去原来的第一个数，以便下次的操作
            }
        }
    }
}
运行结果：
1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 3 2 
1 4 2 3 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 3 1 
2 4 1 3 
3 2 1 4 
3 2 4 1 
3 1 2 4 
3 1 4 2 
3 4 1 2 
3 4 2 1 
4 2 3 1 
4 2 1 3 
4 3 2 1 
4 3 1 2 
4 1 3 2 
4 1 2 3 
时间复杂度：
O(n!)
空间复杂度：
O(1)

递归法思路：

树的高度即节点子树的高度+1（节点子树的高度即左子树高度，右子树高度的最大值）

代码如下：

// Height_Recursive 递归法求树的高度
int Height_Recursive(TreeNode* pTree) {
    if (pTree == NULL) 
    {
        return 0;
    }
    // 分别求出左子树,右子树的高度,取最大值+1
    int leftHeight = Height_Recursive(pTree->left);
    int rightHeight = Height_Recursive(pTree->right);
    return (leftHeight > rightHeight ? leftHeight: rightHeight)+1;
}

非递归法思路：

借鉴程序遍历的思想，一层层的遍历，累加层数即可得到树的高度

代码如下：

// Height_No_Recursive 非递归法求树的高度
// 思路:借鉴层序遍历的思想,一层层的遍历,层数即高度
int Height_No_Recursive(TreeNode* pTree) {
    if (pTree == NULL) 
    {
        return 0;
    }
    queue<TreeNode*> que;
    que.push(pTree);
    int height = 0;
    TreeNode* p = NULL;
    while(!que.empty())
    {
        height++;
        // 该层的节点个数,压入所有节点的孩子节点
        int num = que.size();
        for (int i=0;i<num;i++)
        {
            p = que.front();
            que.pop();

            if (p->left != NULL)
            {
                que.push(p->left);
            }
            if (p->right != NULL)
            {
                que.push(p->right);
            }
        }
    }
    return height;
}

实验结果如下图：



完整代码如下：

#include<iostream>
#include<queue>
using namespace std;

// 树(节点)定义
struct TreeNode 
{
	int		    data; // 值
	TreeNode*	left; // 左节点
	TreeNode*	right;// 右节点
};

// 按照前序建立二叉树，这里我们建立下面的树
//			8
//		6		10
//	  4	  7			12
//                11
// 所以输入顺序是：8 6 4 0 0 7 0 0 10 0 12 11 0 0 0
void createTree(TreeNode*& t)
{	
	cout<<"请输入数据："<<endl;
	int val = 0;
	cin>>val;
 
	// 0表结束
	if (0 == val)
	{
		t = NULL;
	}
	else 
	{
		t = new TreeNode();
		t->data = val;
		cout<<"开始建立:"<<val<<"的左节点：";
		createTree(t->left);
		cout<<"开始建立:"<<val<<"右节点：";
		createTree(t->right);
	}
}

// Height_Recursive 递归法求树的高度
int Height_Recursive(TreeNode* pTree) {
    if (pTree == NULL) 
    {
        return 0;
    }
    // 分别求出左子树,右子树的高度,取最大值+1
    int leftHeight = Height_Recursive(pTree->left);
    int rightHeight = Height_Recursive(pTree->right);
    return (leftHeight > rightHeight ? leftHeight: rightHeight)+1;
}

// Height_No_Recursive 非递归法求树的高度
// 思路:借鉴层序遍历的思想,一层层的遍历,层数即高度
int Height_No_Recursive(TreeNode* pTree) {
    if (pTree == NULL) 
    {
        return 0;
    }
    queue<TreeNode*> que;
    que.push(pTree);
    int height = 0;
    TreeNode* p = NULL;
    while(!que.empty())
    {
        height++;
        // 该层的节点个数,压入所有节点的孩子节点
        int num = que.size();
        for (int i=0;i<num;i++)
        {
            p = que.front();
            que.pop();

            if (p->left != NULL)
            {
                que.push(p->left);
            }
            if (p->right != NULL)
            {
                que.push(p->right);
            }
        }
    }
    return height;
}

int main()
{
    TreeNode* pTree = NULL;
	createTree(pTree);

    cout<<"\n递归法求树的高度"<<endl;
    cout<<Height_Recursive(pTree)<<endl;
   
    cout<<"\n非递归法求树的高度"<<endl;
    cout<<Height_No_Recursive(pTree)<<endl;

    return 0;
}

 

递归法思路：

建立一个数组,count[1]表第1层节点总数,即宽度,count[2]表第二层节点总数,依次类推

用先序遍历二叉树,每深入一层就把该层的节点个数加1,最大节点数即树的宽度

代码如下：

// Width_No_Recursive 非递归法求树的宽度
// 思路:借鉴层序遍历的思想,一层层的遍历,所有层中最大宽度,即树的宽度
int Width_No_Recursive(TreeNode* pTree) {
    if (pTree == NULL) 
    {
        return 0;
    }

    queue<TreeNode*> que;
    que.push(pTree);

    int max_weight = 1;
    TreeNode* p = NULL;
    while(!que.empty())
    {
        // 该层的节点个数,即该层的宽度
        // 弹出该层的节点后,再压入所有节点的孩子节点,即下一层的节点
        int num = que.size();
        if (num > max_weight) 
        {
            max_weight = num;
        }
        for (int i=0;i<num;i++)
        {
            p = que.front();
            que.pop();

            if (p->left != NULL)
            {
                que.push(p->left);
            }
            if (p->right != NULL)
            {
                que.push(p->right);
            }
        }
    }
    return max_weight;
}

非递归法思路：

借鉴层序遍历的思想,一层层的遍历,所有层中最大宽度,即树的宽度

代码如下：

// 统计第level层的节点树
void width(TreeNode* pTree, int* count, int level, int& max) 
{
    if (pTree == NULL)
    {   
        return;
    }
    // 该层次节点数加1
    count[level]++;
    // max一直保存最大宽度
    if (count[level] > max)
    {
        max = count[level];
    }
    // 往下层递归
    width(pTree->left,count,level+1,max);
    width(pTree->right,count,level+1,max);
}

// Width_Recursive 递归法求树的宽度
// 思路:建立一个数组,count[1]表第1层节点总数,即宽度,count[2]表第二层节点总数,依次类推
// 用先序遍历二叉树,每深入一层就把该层的节点个数加1,最大节点数即树的宽度
int Width_Recursive(TreeNode* pTree) 
{
    if (pTree == NULL) 
    {
        return 0;
    }
    int count[100] = {0};   // 全局数组
    int max = 0;            // 宽度

    //递归求树的最大宽度
    width(pTree,count,1,max);
    return max;
}

实验结果如下图：



完整代码如下：

#include<iostream>
#include<queue>
using namespace std;

// 树(节点)定义
struct TreeNode 
{
	int		    data; // 值
	TreeNode*	left; // 左节点
	TreeNode*	right;// 右节点
};

// 按照前序建立二叉树，这里我们建立下面的树
//			8
//		6		10
//	  4	  7			12
//                11
// 所以输入顺序是：8 6 4 0 0 7 0 0 10 0 12 11 0 0 0
void createTree(TreeNode*& t)
{	
	cout<<"请输入数据："<<endl;
	int val = 0;
	cin>>val;
 
	// 0表结束
	if (0 == val)
	{
		t = NULL;
	}
	else 
	{
		t = new TreeNode();
		t->data = val;
		cout<<"开始建立:"<<val<<"的左节点：";
		createTree(t->left);
		cout<<"开始建立:"<<val<<"右节点：";
		createTree(t->right);
	}
}

// 统计第level层的节点树
void width(TreeNode* pTree, int* count, int level, int& max) 
{
    if (pTree == NULL)
    {   
        return;
    }
    // 该层次节点数加1
    count[level]++;
    // max一直保存最大宽度
    if (count[level] > max)
    {
        max = count[level];
    }
    // 往下层递归
    width(pTree->left,count,level+1,max);
    width(pTree->right,count,level+1,max);
}

// Width_Recursive 递归法求树的宽度
// 思路:建立一个数组,count[1]表第1层节点总数,即宽度,count[2]表第二层节点总数,依次类推
// 用先序遍历二叉树,每深入一层就把该层的节点个数加1,最大节点数即树的宽度
int Width_Recursive(TreeNode* pTree) 
{
    if (pTree == NULL) 
    {
        return 0;
    }
    int count[100] = {0};   // 全局数组
    int max = 0;            // 宽度

    //递归求树的最大宽度
    width(pTree,count,1,max);
    return max;
}

// Width_No_Recursive 非递归法求树的宽度
// 思路:借鉴层序遍历的思想,一层层的遍历,所有层中最大宽度,即树的宽度
int Width_No_Recursive(TreeNode* pTree) {
    if (pTree == NULL) 
    {
        return 0;
    }

    queue<TreeNode*> que;
    que.push(pTree);

    int max_weight = 1;
    TreeNode* p = NULL;
    while(!que.empty())
    {
        // 该层的节点个数,即该层的宽度
        // 弹出该层的节点后,再压入所有节点的孩子节点,即下一层的节点
        int num = que.size();
        if (num > max_weight) 
        {
            max_weight = num;
        }
        for (int i=0;i<num;i++)
        {
            p = que.front();
            que.pop();

            if (p->left != NULL)
            {
                que.push(p->left);
            }
            if (p->right != NULL)
            {
                que.push(p->right);
            }
        }
    }
    return max_weight;
}

int main()
{
    TreeNode* pTree = NULL;
	createTree(pTree);

    cout<<"\n递归法求树的宽度"<<endl;
    cout<<Width_Recursive(pTree)<<endl;
   
    cout<<"\n非递归法求树的宽度"<<endl;
    cout<<Width_No_Recursive(pTree)<<endl;

    return 0;
}

 

用递归法和非递归法实现n的阶乘

#include <stdio.h>

int fac(int n) //递归
{
	if(n<0)
	{
		printf("n<0,data error!\n");
	}
	else if(n==0 || n==1) return 1;
	else
	{
		return n*fac(n-1);
	}
	return 0;
}

int fac_f(int n) //非递归
{
	int sum=1;
	for(;n>0;n--)
	{
		sum *=n;
	}
	return sum;
}


int main()
{
	int n,ret=0,ret2=0;
	printf("input an interger number:\n");
	scanf("%d",&n);
	ret=fac(n);
	ret2=fac_f(n);
	printf("递归法：%d!= %d\n",n,ret);
	printf("非递归法：%d!= %d\n",n,ret2);
	return 0;
}