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


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

查看所有标签

猜你喜欢:

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

Java in a Nutshell, 6th Edition

Java in a Nutshell, 6th Edition

Benjamin J Evans、David Flanagan / O'Reilly Media / 2014-10 / USD 59.99

The latest edition of Java in a Nutshell is designed to help experienced Java programmers get the most out of Java 7 and 8, but it's also a learning path for new developers. Chock full of examples tha......一起来看看 《Java in a Nutshell, 6th Edition》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

MD5 加密
MD5 加密

MD5 加密工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器