函数递归和动态内存初识

函数递归

递归函数是数论函数的一种,其定义域与值域都是自然数集,只是由于构作函数方法的不同而有别于其他的函数。处处有定义的函数叫做全函数，未必处处有定义的函数叫做部分函数。最简单又最基本的函数有三个:零函数O(x)=0(其值恒为0);射影函数；后继函数S(x)=x+1。它们合称初始函数。要想由旧函数作出新函数，必须使用各种算子。

那么函数递归就是在函数的参数包含问题规模，在函数的内部直接或者间接调用原函数，其核心思想就是分解与合并

例如我们实现一个n位数的和

int gets(int n) {
	int count = 0;
	for (int i = 1; i <= n; i++) {
		count += i;
	}
	return count;
}
int main() {
	int n=4;
	int res = gets(n);
	printf("%d", res);

}

 这一个简单的函数，那么如果我们用递归的思想处理这个问题应该如何思考呢

依据思想，先分解

 那么这样就把分解成了这样，递归结束的条件是当n=1的时候结束

 

那么这就是他的一个代码的递归过程

再例如，用递归实现二分查找算法，获取一个整形的各个位数并输出

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include<assert.h>
#include<string.h>
int  binarysearch(int* arr, int front, int end, int mid, int value) {
	assert(arr != NULL && front <= mid);
	while (front <= end) {
		if (value == arr[mid]) {
			return mid;
		}

		if (value < arr[mid]) {

			end = mid - 1;
			mid = (front + end) / 2;
			return binarysearch(arr, front, end, mid, value);




		}

		else {

			front = mid + 1;
			mid = (front + end) / 2;
			return binarysearch(arr, front, end, mid, value);
		}
	}
	return -1;
		
	}
int main() {
	int arr[] = { 1,2,3,4,5,6,7,8 };
	int value = 0;
	int front = 0;
	int end = sizeof(arr) / sizeof(arr[0]) - 1;
	int mid = end / 2;
	int  res = binarysearch(arr, front, end, mid, value);
	printf("%-5d", res);
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include<assert.h>
#include<string.h>
void  getnum(int n) {
	int num = 0;
	if (n != 0) {
printf("%5d", n % 10);
getnum(n / 10);
	}
	
}
int main() {
	int n = 123;
	 getnum(n);

}

这些都是比较经典的递归问题

递归的特点和优点

特点

1. 每一级函数调用时都有自己的变量，但是函数代码并不会得到复制，如计算5的阶乘时每递推一次变量都不同；
2. 每次调用都会有一次返回，如计算5的阶乘时每递推一次都返回进行下一次；
3. 递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序；
4. 递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反；
5. 递归函数中必须有终止语句。
 

优点

就是可以代替循环，循环可以干的递归也可以，但是递归能干的循环不一定可以

动态内存

这里就涉及到了函数的调用机制

栈和堆

 

在使用堆进行内存申请的时候，一般会用到malloc函数，在使用malloc函数后，要用free释放掉申请的内存，并且将这块内存空间置空。