简单理解什么是递归(阶乘演示)

你的名字 2022-03-26 05:26 229阅读 0赞

在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。  
一个数的[阶乘][Link 1]来演示递归  
4！= 4 \* 3 \* 2 \* 1

一般情况下我们可能会这样写：

result = 1
    num = 1
    while num < 5:
        result *= num
        num += 1
    print(f"4的阶乘结果为：{result}")
    
    pycharm中执行结果：
    	4的阶乘结果为：24

使用递归：

def get_num(number):
        if number > 1:
            return number * get_num(number - 1)
        else:
            return number
    
    
    result = get_num(4)
    print("4的阶乘结果为：%s" % result)
    
    pycharm中执行结果：
    	4的阶乘结果为：24

画图理解：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYTY0NzYwMDM_size_16_color_FFFFFF_t_70][]

文字理解：

===> get_num(4)
    ===> 4 * get_num(3)
    ===> 4 * (3 * get_num(2))
    ===> 4 * (3 * (2* get_num(1)))
    ===> 4 * (3 * (2 * (1 * 1)))
    ===> 4 * (3* (2 * 1))
    ===> 4 * (3 * 2)
    ===> 4 * 6
    ===> 24

递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。

**注意：** 使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

示例代码：

def demo():
        print("test...")
        demo()
    
        
    demo()

上面的代码类似于写了个while True 没有写结束循环的条件。

**实例：**

/* * 递归实现n个子母随机组合每次输出n个子母(每次输出不同组合直至输出所有组合结果) * */
    public class TestRecursive { 
    	public static void main(String[] args) { 
    		char[] chs = {  'a', 'b', 'c' };
    		int number = 2; // 每次输出几个字符
    		arrange(chs, 0, chs.length, number);
    
    	}
    
    	public static void arrange(char[] chs, int start, int len, int number) { 
    		if (start == len - 1) { 
    			for (int i = 0; i < number; i++) { 
    				System.out.print(chs[i]);
    			}
    			System.out.println();
    			return;
    		}
    		for (int i = start; i < len; i++) { 
    			char temp = chs[start];
    			chs[start] = chs[i];
    			chs[i] = temp;
    			arrange(chs, start + 1, len, number);
    			temp = chs[start];
    			chs[start] = chs[i];
    			chs[i] = temp;
    
    		}
    	}
    }
    
    eclipse中执行结果：
    	ab
    	ac
    	ba
    	bc
    	cb
    	ca

[Link 1]: https://baike.baidu.com/item/%E9%98%B6%E4%B9%98/4437932?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYTY0NzYwMDM_size_16_color_FFFFFF_t_70]: /images/20220326/f6442d42ecca432ab668641e40dc4eec.png