C语言之通俗易懂的递归算法

栏目: C · 发布时间: 5年前

内容简介:记得大学接触的第一门课程就是C语言,里面让我印象深刻之一就是递归,受大学老师讲递归的启发我尝试着用最通俗、最易懂的方式讲解递归。递归其实真的不难。觉得递归很难的朋友,可以试试看一下,相信如果你能认真的看完这篇文章,或许会有很大的收获

C语言之通俗易懂的递归算法

摘要

记得大学接触的第一门课程就是C语言,里面让我印象深刻之一就是递归,受大学老师讲递归的启发

我尝试着用最通俗、最易懂的方式讲解递归。递归其实真的不难。觉得递归很难的朋友,可以试试看一下,相信如果你能认真的看完这篇文章,或许会有很大的收获

递归产生条件

递归两个必要条件:

**1.递归函数** 
**2.递归出口**

下面的练习会让你清晰的发现,递归其实就是要找 递归函数和递归出口 这两步

练习

假设有个数列 1 3 5 7 9 11 .... 找到第n项的值

逻辑分析:

C语言之通俗易懂的递归算法

递归函数:f(n) = f(n-1)+2;

递归出口:f(1) = 1;

代码实现

/**
     假设有个数列 1 3 5 7 9 11 ....
    
     递归函数:f(n) = f(n-1)+2;
     递归出口: f(1) = 1;
     
     @param n 求n项的值
     @return 返回第n项的值
     */
    int find(int n) {
        if (n == 1) {// 递归出口
            return 1;
        } else {//递归函数
            return find(n-1)+2;
        }
    }

Fibonacci 斐波那契数列

逻辑分析:

C语言之通俗易懂的递归算法

递归函数:fibonacci(n) = fibonacci(n-1)+fibonacci(n-2)

递归出口:fibonacci(1) = 1,fibonacci(2) = 1;

代码实现

/**
     fibonacci 斐波那契数列
     1 1 2 3 5 8 13 21 ....
     
    递归函数:fibonacci(n) = fibonacci(n-1)+fibonacci(n-2)
    递归出口:fibonacci(1) = 1,fibonacci(2) = 1;
     
     @param n 求第n项
     @return 返回第n项的值
     */
    int fibonacci (int n) {
        if (n==1 || n==2) { // 递归出口
            return 1;
        } else { //递归函数
            return fibonacci(n-1)+fibonacci(n-2);
        }
        return 0;
    }

有序数列求和:1+2+3+4+...+100

逻辑分析:

C语言之通俗易懂的递归算法

递归函数:sum(n) = sum(n-1)+n

递归出口:f(1) = 1

代码实现

/**
     //有序数列
     求和:1+2+3+4+...+100
     
     递归函数:sum(n) = sum(n-1)+n
     递归出口:f(1) = 1
    
     @param n 前n项
     @return 返回 前n项的和
     */
    int sum(int n) {
        if (n == 1) {
            return 1;
        } else {
            return sum(n-1)+n;
        }
    }

无序数列求前n项的和:{1, 7, 8, 6, 8, 9, 0, 10}

逻辑分析:

C语言之通俗易懂的递归算法

递归函数:sum1(arr,n) = sum1(arr,n-1)+arr[n];

递归出口:sum1(arr,0) = arr[0]

代码实现

/**
     //无序数列
     求前n项的和:int arr[] = {1, 7, 8, 6, 8, 9, 0, 10}
    
     递归函数:sum1(arr,n) = sum1(arr,n-1)+arr[n];
     递归出口:sum1(arr,0) = arr[0]
     
     @param arr 数组
     @param n 求数组中第几项
     @return 返回中前n项的和
     */
    int sum1(int arr[], int n) {
        if (n == 0) {
            return arr[0];
        } else {
            return sum1(arr,n-1)+arr[n];
        }
    }

无序数列求数组中前n项的最大值

逻辑分析:

C语言之通俗易懂的递归算法

C语言之通俗易懂的递归算法

递归函数:

if (findMaxNum(arr, n-1) > arr[n]) {
           return findMaxNum(arr, n-1);
        } else {
           return arr[n];
       };

递归出口: n == 0 return arr[0];

代码实现

/**
     //无序数列
     求数组中前n项的最大值:int arr1[] = {7, 4, 8, 6, 8, 9, 11, 5}
     
     递归函数:      if (findMaxNum(arr, n-1) > arr[n]) {
                        return findMaxNum(arr, n-1);
                   } else {
                        return arr[n];
                   };
     递归出口:n == 0 return arr[0];
    
     @param arr 数组
     @param n 求数组中前n项的最大值
     @return 返回数组中前n项的最大值
     */
    int findMaxNum(int arr[], int n) {
        if (n == 0) {
            return arr[0];
        } else if (findMaxNum(arr, n-1) > arr[n]) {
            return findMaxNum(arr, n-1);
        } else {
            return arr[n];
        }
    }

测试功能

int num ;
       
        num = find(6);
        printf("第6项的值为%d\n",num);
        
        num = fibonacci(6);
        printf("第6项的值为%d\n",num);
        
        num = sum(100);
        printf("前100项的和为%d\n",num);
        
        int arr[] = {1, 7, 8, 6, 8, 9, 0, 10};
        num = sum1(arr,7);
        printf("前7项的和为%d\n",num);
        
        int arr1[] = {7, 4, 8, 6, 8, 9, 11, 5};
        num = findMaxNum(arr1, 7);
        printf("前7项的最大值为%d\n",num);

输出结果

C语言之通俗易懂的递归算法

不积跬步,无以至千里

当我们踏上一条路,便不要再问路有多遥远,处境是否坎坷。我们不断的走走停停,繁华的是风景,荒芜的是岁月。

源码地址:

Recursion


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Convergence Culture

Convergence Culture

Henry Jenkins / NYU Press / 2006-08-01 / USD 30.00

"Convergence Culture" maps a new territory: where old and new media intersect, where grassroots and corporate media collide, where the power of the media producer, and the power of the consumer intera......一起来看看 《Convergence Culture》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

URL 编码/解码
URL 编码/解码

URL 编码/解码

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具