递归和尾递归的运行流程解释

共计 2600 个字符，预计需要花费 7 分钟才能阅读完成。

递归（英语：recursion）在计算机科学中是指一种 通过重复将问题分解为同类的子问题而解决问题的方法。[1] 递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。[2] 绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此有很多在函数编程语言（如 Scheme）中用递归来取代循环的例子。(摘自维基百科)

在计算机学里，尾调用 是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。[1]此时，该尾部调用位置被称为尾位置。尾调用中有一种重要而特殊的情形叫做尾递归 。经过适当处理， 尾递归 形式的函数的运行效率可以被极大地优化。[1]尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化（称为“尾调用消除”），但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度如何。(摘自维基百科)

递归我将它分为两个过程, 一个我将它称为递归 , 另一个我将它称为回溯 . 递归的函数的运行主要有这两个流程, 递归的进入, 回溯的退出, 这 两个过程的分界是以递归出口为分界的.
递归的实现形式是使用栈, 递归函数的进入 (递归) 类似与压栈 , 递归函数的退出(回溯) 类似于出栈.

【编程题】幂运算三（递归函数 ）
题目 ID：1137
【问题描述】求 x^n。
【输入形式】一行 2 个数，第一个整数表示 x，第二个大于等于零的整数表示 n，二数之间用空格分隔。
【输出形式】一行一个整数，表示 x 的 n 次方
【样例输入】2 3
【样例输出】8

【样例说明】2 的 3 次方结果为 8
【评分标准】5 组测试用例，每组 2 分，共计 10 分

【测试用例】
1）
输入：
2 3
输出：
8
2）
输入：
3 5
输出：
243

3）
输入：
-17 4
输出：
83521

4）
输入：
22 0
输出：
1

5）
输入：
-1287 0
输出：
1

// 普通递归
#include<stdio.h>
long my_pow1(long x,int n){if(n==0) return 1;      // 递归出口
    return x*(my_pow1(x,--n));  // 除了调用自身外还乘多了个 x, 即一般的递归
}
int main(){
    long  x;
    int  n;
    scanf("%ld%d",&x,&n);
    printf("%ld\n",my_pow1(x,n));
    return 0;
}

运行图解

解释:
普通的递归过程是在一个函数中,结果依靠自身的调用来得出 , 例如求幂运算,pow(2,3) 代表求 2 的 3 次方, 由于 pow(2,3) 未知, 我们可以把它分解成 2*pow(2,2),pow(2,2) 也未知, 又可分解成 2 *pow(2,1), 以此类推, 直到 pow(2,0)可知 (if 中定义 0 时返回 1), 即 pow(2,0) 返回值是 1.
在这个递归过程中,pow 函数的建立就是一个个压栈的过程
我把它称为函数栈

压栈压入所以函数后, 直到最后一个, 可以 获得最后一个函数的返回值 , 由这个返回值可以 依次推出栈内所有函数的返回值 (回溯), 即退栈,pow(2,0)返回 1, 推的 pow(2,1)返回 2 *pow(2,0), 即 2 *1=2,pow(2,2)返回 2 *pow(2,1), 即 2 *2=4, 直到退到栈内最后一个函数 pow(2,3), 可获得 pow(2,3)的返回值为 2 *pow(2,2)即 8;

【编程题】吃糖（尾递归函数 ）
题目 ID：1135
【问题描述】小樱是个爱吃糖的女孩, 哥哥送了她 n（1<=n<=30）颗糖，怎么吃？一天吃 1 颗；一天吃 2 颗。嗯，那就每天吃一颗或两颗吧。
1 颗糖，肯定只有（1）一种吃法；2 颗糖，有（1，1）和（2）两种吃法；3 颗糖，有（1，1，1）、（1，2）和（2，1）三种吃法。注（2，1）表示第一天吃 2 颗，第二天吃 1 颗。*
你能帮小樱算出，吃完这 n 颗糖，有多少种吃法吗？请编写一个尾递归函数来解决此问题
【输入形式】

【测试用例】
1）
输入：
1
输出：
result=1

2）
输入：
4
输出：
result=5

3）
输入：
15
输出：
result=987

4）
输入：
20
输出：
result=10946

5）
输入：
30
输出：
result=1346269

实际上这道题是一 个斐波那契数列的变体, 可用尾递归函数解决

// 尾递归
#include <stdio.h>
int ci(int n,int pre,int next)
{
    int sum;
    if (n==1){// 递归出口(递归和回溯的分界点)
        return pre;
    }
    return ci(n-1,next,pre+next);  // 除了调用自身外没有其他操作即为尾递归
}
int main()
{
    int n;
    int sum;
    scanf ("%d",&n);
    printf ("result=%d",ci(n,1,2));
    return 0;
}

运行图解

解释:

尾递归是属于递归的 , 它也有递归和压栈两个过程, 但是由于 尾递归除了调用自身外没有任何其他多余的操作 , 所以它在进行到递归出口的时候, 获得一个 返回值 , 进行回溯的每一个函数的返回值都是它的调用的另一个规模缩小的函数, 也就是说: 函数在压栈的时候, 压到栈顶函数, 获得一个返回值, 退栈, 当前栈顶获得返回值, 这个值是退栈的那个元素的返回值, 依次类推, 直到所有函数退栈, 获得的返回值都是一个值, 也就是递归出口的那个值.
用例子来表示, 即是回溯过程中,ci(1,5,8)获得了返回值 5,ci(2,3,5)的返回值是 ci(1,5,8), 也就是 5,ci(3,2,3)的返回值是 ci(2,3,5), 也就是 5,ci(4,1,2)的返回值也是 5;
从尾递归的流程中可以看出,尾递归的回溯的过程是完全没用的, 直到递归出口就已经获得了想要的值了.
递归的过程也只是相当于循环 而已,ci(4,1,2),4 是要求斐波那契变体的第 4 项,1 是第一项,2 是第二项, 从 4 减到 1 起到一个计数作用,1 和 2 也是作为递推的起点
所以, 在很多语言中,尾递归可被优化成和循环 (递推) 一样的效率.

递归有两个过程,递归和回溯, 递归到最深处获得一个返回值, 由这个返回值回溯推出想要求的函数的返回值, 起到缩小规模计算的作用.
尾递归与递归的 不同处在于尾递归在 return 处除了调用自身外没有其他操作, 导致回溯的过程是完全浪费的.
尾递归在一些语言中可以 优化成和循环一样的执行效率.

* 下图是普通递归和尾递归的执行图示: