递归思想

文章目录

• 1.创造递归把握两个点

• 2.递归和循环的生动解释

• 3.递归思想的内涵(递归的精髓是什么？)

• • 3.1递去
  • 3.2归来
  • 3.2 递归思想的精髓

• 4.递归的应用场景

• 5.用代码加深理解

1.创造递归把握两个点

• 递归出口
• 分解为子问题，将大规模问题缩小

2.递归和循环的生动解释

引用自知乎用户李继刚(https://www.zhihu.com/question/20507130/answer/15551917)。

递归：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。

循环：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门（若前面两扇门都一样，那么这扇门和前两扇门也一样；如果第二扇门比第一扇门小，那么这扇门也比第二扇门小，你继续打开这扇门，一直这样继续下去直到打开所有的门。但是，入口处的人始终等不到你回去告诉他答案。

3.递归思想的内涵(递归的精髓是什么？)

3.1递去

正如上面所描述的场景，递归就是有去（递去）有回（归来），如下图所示。“有去”是指：递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决，就像上面例子中的钥匙可以打开后面所有门上的锁一样；

3.2归来

“有回”是指 : 这些问题的演化过程是一个从大到小，由近及远的过程，并且会有一个明确的终点(临界点)，一旦到达了这个临界点，就不用再往更小、更远的地方走下去。最后，从这个临界点开始，原路返回到原点，原问题解决。

3.2 递归思想的精髓

将问题逐一递过去（即子问题承担递问题的角色）并不解决，直到到达临界条件（即递归出口），然后回溯（即原路返回）去一一解决。

4.递归的应用场景

在我们实际学习工作中，递归算法一般用于解决三类问题：

(1). 问题的定义是按递归定义的（Fibonacci函数，阶乘，…）；

(2). 问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；

(3). 数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）。

5.用代码加深理解

eg1:
打印二叉树，它可看作特殊的中序遍历，中序遍历是LDR遍历，打印二叉树是RDL。

    //逆时针旋转90°打印二叉树root，n为缩进层数，初始值为0
    void PrintBiTree(BiTreeNode *root, int n)   
    {
    	int i;
    	if(root == NULL)  return;  //递归出口
    	PrintBiTree(root->rightChild, n+1);
    	
    	//访问根结点
    	for(i = 0; i < n-1;i++) printf("   "); 
    	if(n > 0)
    	{   
    		printf("----");  
    		printf("%c\n", root->data);   
    	}
    	PrintBiTree(root->leftChild, n+1);    
    }
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    

eg2:
汉诺塔

    int move(int n,char x,char y,char z)
    {
    if(n==1)
        printf("%c-->%c\n" ,x,z);
    else
    {
        move(n-1,x,z,y);
        printf("%c-->%c\n" ,x,z);
        move(n-1,y,x,z);
    }
    return 0;
    }