【程序基础】递归法

递归法"/>

【程序基础】递归法

算法思想

递归法，其实可以说是一种编程技巧，通过调用自身，防止无限循环而给予递归出口。

思考使用场景

1.一个问题可以拆分成子问题，每个子问题相互独立。
2.数据满足递推关系，或者数据结构满足，例如图，树，链表数组等。

简单的示例

示例1，比如做一次递归遍历，把字符串数组里面的元素逐一输出。

 void showStr(int len,int i,char* arr){if(arr == nullptr || i >= len){return;}showStr(len,i+1,arr);cout << arr[i] << endl;}

示例2，计算斐波那契数列，1、1、2、3、5、8、
可以知道f(n) = f(n - 1) + f(n - 2)，这里可以满足把f(n)拆分成n个f(1)+f(2)切每个独立

 int fbnac(int n){if(n==1 || n==2){return 1;}return fbnac(n - 1) + fbnac(n - 2);}