文章目录
  1. 1. 递归
    1. 1.1. 递归的概念
    2. 1.2. 递归的实现
    3. 1.3. 递归实现原理

递归

递归的概念

最基础的一个算法,递归的作用很强,并且在我们所存在的大自然中递归的现象是很多的,最简单的例子,相信也肯定见过,就是两个镜子相对,镜子中的样子是什么样的?这就是说她允许一个对象以其自身更小的形式来定义自己。

递归是以递归函数来实现的。什么叫递归函数?递归函数就是一种可以调用自身的函数。每一次的调用都可以让数据更加清晰,让我们距离正确的数据更加近,输入变得更加的清晰。

递归的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//
// main.cpp
// recursion
//
// Created by LastDays on 16/5/18.
// Copyright © 2016年 LastDays. All rights reserved.
//

#include <iostream>
using namespace std;

/**
* 递归函数
*
* @param n 阶层
*
* @return 返回结果
*/
int fact(int n){
if (n<0) {
return 0;
}else if (n==0){
return 1;
}else if (n==1){
return 1;
}else{
return n*fact(n-1);
}
}

int main(int argc, const char * argv[]) {
// insert code here...
int n = 0;
cin>>n;
cout<<"结果:"<<fact(n)<<endl;

return 0;
}

递归实现原理

很多人都是知道如何写递归,但是并不知道递归更深层次的实现原理,首先就需要先了解下一个程序的结构,一个程序包含四个部分:代码段、静态数据区、堆、栈。详细介绍下堆,跟栈。堆中包含着程序运行时动态分配的存储空间,二栈中包含函数的调用信息。基本上,在Windows中堆的增长方式为从底地址到搞地址,栈确是相反的结构。

刚才说到了,栈中包含着函数的调用信息,也就是说当我们的fact函数调用时,会在栈中分配一个空间来保存它的调用相关的信息。栈上的那块存储空间被称为栈帧。

栈帧有5个部分:输入参数,返回值空间,计算表达式时用到的临时空间,函数调用是保存的状态信息,输出参数

输入参数指的就是fact(n)中的n,输出参数就是指的栈帧中调用的函数所使用的,一个栈帧中的输出参数将会成为下一个栈帧的输入函数,函数调用产生的栈帧将会一直保留在栈中直到函数调用结束。

举个例子:fact(4),n=4为一个输入参数,不满足条件,将会继续使用n=3作为参数,此时就会在栈上创建另一个栈帧,就是说4为第一个栈帧的出入参数,3为第一个栈帧的输出参数,当创建了新的栈帧的时候,3就是第二个栈帧的输入参数,2就是第二个栈帧的输出参数,一次类推,直到满足结果为止。一旦满足结果就将会结束每一个栈帧的活跃期。递归结束,释放栈中函数调用信息。

文章目录
  1. 1. 递归
    1. 1.1. 递归的概念
    2. 1.2. 递归的实现
    3. 1.3. 递归实现原理