函数与递归（day9）

本章目的不是为了学会递归，而是通过递归学习函数在递归过程中在内存的储况以及递归函数的语句执行顺序。

问题1：通过递归拆分数字

实例

​void print(int x)

{
  if (x > 9)
  {
  print(x / 10);
  }
  printf("%d\t", x % 10);
}

int main()

{
  int num;
  scanf("%d", &num);
  print(num);
  return 0;
}

在本次实例中，我们设置了一个名为print的函数，使其能够打印输入值的每一位数字。我们采用递归的思路

以输入123为例：

（123）

（12） 3

（1）  2    3

1      2         3

每次我们除以十，得到最后一位，以此类推，直到得到最后一位（首位）小于10时，跳出函数分别打印。

设置函数代码如下：

void print(int x)


{
  if (x > 9)
  {
  print(x / 10);
  }
  printf("%d\t", x % 10);
}

此递归函数的执行顺序如下：

我们假设print型参接到的值为123，

1. 调用print，型参向栈区申请（内存区域1）储存123
2. 进入函数，执行判断：123>9
3. 返回值为1，调用print，型参向栈区申请（内存区域2）储存12
4. 进入函数，执行判断：12>9
5. 返回值为1，调用print，型参向栈区申请（内存区域3）储存1
6. 进入函数，执行判断：1>9
7. 返回值为0，执行打印命令，读取（区域3）储存的值，打印1%10的值为”1“。跳出第三次执行的print函数进入第二次执行的print函数。
8. 读取（区域2）储存的值，打印12%10的值为”2“。跳出第二次执行的print函数进入第一次执行的print函数。
9. 读取（区域1）储存的值，打印123%10的值为”3“.跳出第一次执行的print函数。
10. 函数执行完毕。

通过以上顺序我们就清楚了，为何递归时会出现栈溢出的错误。因为型参会不断向内存申请空间储存函数运行中的中间值。

问题2：​不用变量实现读取字符串长度的函数

实例

​int str_len(char* str)

{

  if (*str != '\0')

  return (1 + str_len(str + 1));

  else

  return 0;

}


int main()

{

  char arr[] = "bit";

  int len = str_len(arr);

  printf("%d\n", len);

  return 0;

}

需要注意，数组传参传递的是首元素的地址。而数组元素与元素之间的地址是紧密相连的。

现在我们来看这个递归函数：

int str_len(char* str)
{
if (*str != '\0')
return (1 + str_len(str + 1));
else
return 0;
}

我们给char型数组第赋值为”bit“，实际在数组中其分别以”b“，”i“，”t“，”\0“形式储存。现在调用我们定义的str_len函数来得到字符串的长度。我们直接看函数执行逻辑。

1）主函数将数组第一个元素”b“的地址传递给定义函数str_len的型参。

2）第一次：解引用该地址，取出储存的元素，执行判断结果为真，我们将第一层函数返回 1+str_len(str +1),这时候返回的并不是一个确定值，我们第二次调用str_len函数。

3）第二次：我们向该函数返回的是第一个元素地址+1，解引用该地址得到数组中存储的第二个元素”i“，执行判断结果为真，我们将第二层函数返回1+str_len(str +1),这时候返回的并不是一个确定值，我们第三次调用str_len函数。

4）第三次：我们向该函数返回的是第二个元素地址+1，解引用该地址得到数组中存储的第三个元素”t“，执行判断结果为真，我们将第二层函数返回1+str_len(str +1),这时候返回的并不是一个确定值，我们第四次调用str_len函数。

4）第四次：我们向该函数返回的是第三个元素地址+1，解引用该地址得到数组中存储的第三个元素”\0“，执行判断结果为假，我们得到第四次执行函数得到的返回值为0，随后跳出第四次执行的函数。

5）第三次执行的函数得到了第四次函数执行得到确定的返回值0，str_len(str + 1) = 0，根据return表达式，第三次函数执行得到的返回值为1

6）第二次执行的函数得到了第三次函数执行得到确定的返回值1，str_len(str + 1) = 1，根据return表达式，第二次函数执行得到的返回值为2

7）第二次执行的函数得到了第二次函数执行得到确定的返回值2，str_len(str + 1) = 1，根据return表达式，第一次函数执行得到的返回值为3

8）函数得到返回值为3，函数执行完毕。

递归原理确实是一种很天才的方式。