精华内容
下载资源
问答
  • 程序运行,系统每次向栈中压入一个对象,然后栈指针向下移动一个位置。当系统从栈中弹出一个对象,最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进...

    一、栈
         在说函数递归的时候,顺便说一下栈的概念。
         栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时,系统每次向栈中压入一个对象,然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时,最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的,它不需要程序员编写代码去维护,而是由运行是系统自动处理。所谓的系统自动维护,实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们,但程序员应该对此有所了解。
         再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时,运行时系统将把调用者的所有实参和返回地址压入到栈中,栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时,系统把被调用者的自变量压入到栈中,并把栈指针再向下移,以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后,被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作,栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针,以他为参考,用正或负的偏移值来访问栈中的变量。当被调用者准备返回时,系统弹出栈中所有的自变量,这时栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回,系统从栈中弹出返回地址,调用者就可以继续执行了。当调用者继续执行时,系统还将从栈中弹出调用者的实参,于是栈指针回到了调用发生前的位置。
         可能刚开始学的人看不太懂上面的讲解,栈涉及到指针问题,具体可以看看一些数据结构的书。要想学好编程语言,数据结构是一定要学的。

    二、递归
         递归,是函数实现的一个很重要的环节,很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身,或者在自己函数调用的下级函数中调用自己。
         递归之所以能实现,是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝,这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础,是使得递归成为可能。假定某个调用函数调用了一个被调用函数,再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归,因为它发生在调用函数的当前执行过程运行完毕之前。而且,因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量,原先的参数和变量将不受影响,所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。
         程序员需保证递归函数不会随意改变静态变量和全局变量的值,以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程,并且返回到顶层。
         例如这样的程序就是递归:

             void a(int);

             main()
             {
                 int num=5;
                 a(num);
             }

             void a(int num)
             {
                 if(num==0) return;
                 printf("%d",num);
                 a(--num);
             }
            
         在函数a()里面又调用了自己,也就是自己调用本身,这样就是递归。那么有些人可能要想,这不是死循环吗?所以在递归函数中,一定要有return语句,没有return语句的递归函数是死循环。
         我们分析上面的例子,先调用a(5),然后输出5,再在函数中调用本身a(4),接着回到函数起点,输出4,……,一直到调用a(0),这时发现已经满足if条件,不在调用而是返回了,所以这个递归一共进行了5次。如果没有这个return,肯定是死循环的。
         虽然递归不难理解,但是很多在在使用递归函数的时候,问题多多。这里面一般有两个原因:一是如何往下递归,也就是不知道怎么取一个变量递归下去;二是不知道怎么终止递归,经常弄个死循环出来。
         下面看几个例子:
         1.求1+2+……+100的和
             先分析一下。第一递归变量的问题,从题目上看应该取1,2,……,100这些变量的值作为递归的条件;第二就是如何终止的问题,从题目上看应该是当数为100的时候就不能往下加了。那么我们试着写一下程序。

             int add(int);

             main()
             {
                 int num=1,sn;
                 sn=add(num);
                 printf("%d/n",sn);
                 getch();
             }

             int add(int num)
             {
                 static int sn;
                 sn+=num;
                 if(num==100) return sn;
                 add(++num);
             }

         分析一下程序:前调用add(1),然后在子函数中把这个1加到sn上面。接着调用add(2),再把sn加2上来。这样一直到100,到了100的时候,先加上来,然后发现满足了if条件,这时返回sn的值,也就是1+2+……+100的值了。
         这里有一个问题一定要注意,就是static int sn; 
         有些人就不明白,为什么要使用static类型修饰符,为什么不使用int sn=0;?如果使用int sn=0;这样的语句,在每次调用函数add()的时候,sn的值都是赋值为0,也就是第一步虽然加了1上来,可是第二次调用的时候,sn又回到了0。我们前面说了,static能保证本次初始化的值是上次执行后的值,这样也就保证了前面想加的结果不会丢失。如果你修改为int sn=0,最后结果一定是最后的100这个值而不是5050。

         2.求数列s(n)=s(n-1)+s(n-2)的第n项。其中s(1)=s(2)=1。
             可以看出,终止条件一定是s(1)=s(2)=1。递归下降的参数一定是n。

             int a(int);

             main()
             {
                 int n,s;
                 scanf("%d",&n);
                 s=a(n);
                 printf("%d/n",s);
                 getch();
             }

             int a(int n)
             {
                 if(n<3) return 1;
                 return a(n-1)+a(n-2);
             }
            
         这个题目主要说明的是,在函数中,不一定只有一个return语句,可以有很多,但是每次对归的时候只有一个起作用。题目不难理解,这儿不分析了。
         说了这些递归,其实它和函数的调用没有大的区别,主要就是一个终止条件要选好。递归函数很多时候都能用循环来处理。

             main()
             {
                 int n=20,array[20];
                 int i;
                 for(i=0;i<n;i++)
                 {
                     if(i<2) array=1;
                     else array=array+array;
                 }
                 printf("%d/n",array[19]);
                 getch();
             }

         上面的程序就是实现一模一样的功能的。但是它有一个缺陷,就是n的值不是通过键盘输入来得到。如果想通过键盘来得到n,可以这样:

             main()
             {
                 int n,i;
                 int s1=1,s2=1,temp
                 scanf("%d",&n);
                 for(i=3;i<=n;i++)
                 {
                     temp=s2;
                     s2+=s1;
                     s1=temp;
                 }
                 printf("%d/n",s2);
                 getch();
             }

         但是在某些场合,使用递归比使用循环要简单的多。而且有些题目,一看就知道应该使用递归而不是循环来处理。

    转载于:https://www.cnblogs.com/zhq--blog/p/7354056.html

    展开全文
  • 如果在调用一个函数的过程中直接或间接调用自身本身,则称为递归调用 从某种意义上来说,递归调用可以实现无限循环 二、递归调用的特性 必须有一个明确的结束条件 每次进入更深一层递归时,问题规模相比上次...

    一、递归调用定义

    在函数内部,可以调用其他函数。

    如果在调用一个函数的过程中直接或间接调用自身本身,则称为递归调用

    从某种意义上来说,递归调用可以实现无限循环


    二、递归调用的特性

    • 必须有一个明确的结束条件
    • 每次进入更深一层递归时,问题规模相比上次递归都应有所减少
    • 递归效率不高,递归层次过多会导致栈溢出
      • 在计算机中,函数调用是通过栈(stack)这种数据结构实现的
      • 每当进入一个函数调用,栈就会加一层栈帧
      • 每当函数返回,栈就会减一层栈帧
      • 由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出


    三、递归实例

    递归调用就是一个问路的过程。通过一个程序以及其执行过程来更好的理解递归调用

     

     1 import time
     2 person_list = ['Rachel', 'Monica', 'Ross', 'Joey']
     3 def ask_way(person_list):
     4     print('-'*60)
     5     if len(person_list) == 0:
     6         return '没人知道'
     7     person = person_list.pop(0)
     8     if person == 'Ross':
     9         return '%s说:我知道,流水人家就在小桥旁' %person
    10     print('hi 亲爱的%s,知道流水人家在哪里吗?' %person)
    11     print('%s回答道:抱歉,我不知道,我帮你问问%s...' %(person,person_list))
    12     time.sleep(3)
    13     res = ask_way(person_list)
    14     print('%s问的结果是: %res' %(person,res))
    15     return res
    16 res = ask_way(person_list)
    17 print(res)

     

    转载于:https://www.cnblogs.com/guoruxin/p/9920564.html

    展开全文
  • 递归(recursion):递归常被用来描述以自相似方法重复事物的过程数学和计算机科学中,指的是函数定义中使用函数自身的方法。(A调用A) 迭代(iteration):重复反馈过程的活动,每一次迭代的结果会作为下一...

    递归与迭代的区别

    递归(recursion):递归常被用来描述以自相似方法重复事物的过程,在数学和计算机科学中,指的是在函数定义中使用函数自身的方法。(A调用A)

    迭代(iteration):重复反馈过程的活动,每一次迭代的结果会作为下一次迭代的初始值。(A重复调用B)

    递归是一个树结构,从字面可以其理解为重复“递推”和“回归”的过程,当“递推”到达底部时就会开始“回归”,其过程相当于树的深度优先遍历。

    迭代是一个环结构,从初始状态开始,每次迭代都遍历这个环,并更新状态,多次迭代直到到达结束状态。

    理论上递归和迭代时间复杂度方面是一样的,但实际应用中(函数调用和函数调用堆栈的开销)递归比迭代效率要低。
    在这里插入图片描述

    迭代的例子

    在这里插入图片描述

    递归的实例
    在这里插入图片描述

    递归转迭代

    理论上递归和迭代可以相互转换,但实际从算法结构来说,递归声明的结构并不总能转换为迭代结构(原因有待研究)。迭代可以转换为递归,但递归不一定能转换为迭代。

    将递归算法转换为非递归算法有两种方法,一种是直接求值(迭代),不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法,后者使用栈保存中间结果,称为间接转换法。

    直接转换法

    直接转换法通常用来消除尾递归(tail recursion)和单向递归,将递归结构用迭代结构来替代。(单向递归 → 尾递归 → 迭代)

    间接转换法

    递归实际上利用了系统堆栈实现自身调用,我们通过使用栈保存中间结果模拟递归过程,将其转为非递归形式。

    尾递归函数递归调用返回时正好是函数的结尾,因此递归调用时就不需要保留当前栈帧,可以直接将当前栈帧覆盖掉。
    在这里插入图片描述

    斐波那契数列

    递归形式

    斐波那契数列递归式:F(n)=F(n−1)+F(n−2)(n>=2)F(n)=F(n−1)+F(n−2)(n>=2)

    伪代码(递归算法):

    FOB_RECURSION(n)

    ifn ==1or n ==2

    return1

    elsereturnFOB_RECURSION(n -1) + FOB_RECURSION(n -2) // 调用自身

    非递归形式

    直接转换:

    斐波那契数列迭代式:xn=f(xa,xb)(a=n−1,b=n−2,n>=2)xn=f(xa,xb)(a=n−1,b=n−2,n>=2)

    伪代码(迭代算法):

    FOB_ITERATION(n)

    ifn ==1or n ==2

    return1;

    else

    fn1 =1// 初始状态

    fn2 =1// 初始状态

    fn =0

    fori =2to n // 迭代

            fn = fn1 + fn2
    
            fn1 = fn2
    
            fn2 = fn
    

    returnfn

    间接转换框架:

    FUNCTION()

    stack.push(s0) // s0:初始状态
    

    while!stack.empty()

        s = stack.pop()
    

    ifisSolution(s)

    return

    elsestack.push(s1) // s1:相关状态

    展开全文
  • 递归

    热门讨论 2019-08-04 15:09:43
    递归,就是运行的过程中调用自己,每次调用时传入不同的变量。使用递归可以我们解决复杂的问题,同时也使得我们的代码更加简洁。 递归的调用规则: 1.当程序执行一个方法时,就会开辟一个独立的空间(栈) 2.每...

    递归的概念:

    递归,就是在运行的过程中调用自己,每次调用时传入不同的变量。使用递归可以我们解决复杂的问题,同时也使得我们的代码更加简洁。

    递归的调用规则:

    1.当程序执行一个方法时,就会开辟一个独立的空间(栈)
    2.每个空间的数据是(局部变量)独立的,不会相互影响。
    3.如果方法中使用的是引用类型的变量(比如 数组),就会共享该引用类型的数据。
    4.递归必须向退出递归的条件逼近,否则就是无限递归,会出现栈溢出异常。
    5.当一个方法执行完毕,或者遇到return,就会返回,遵循谁调用,就把结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕。

    递归能解决什么问题:
    1.各种数学问题:八皇后问题,汉诺塔,阶乘问题,迷宫问题。。。
    2.各种算法中也会有递归实现:快排,归并排序,二分查找,分治算法。。。
    3.利用栈解决的问题->递归更加简洁。

    递归的使用举例:

    斐波那契数列:
    斐波那契数列,又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……这个数列从第3项开始,每一项都等于前两项之和。
    一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死,那么一年以后可以繁殖多少对兔子?
    我们不妨拿新出生的一对小兔子分析一下:
    第一个月小兔子没有繁殖能力,所以还是一对
    两个月后,生下一对小兔对数共有两对
    三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对。
    。。。
    依次类推可以列出下表:
    在这里插入图片描述
    幼仔对数=前月成兔对数
    成兔对数=前月成兔对数+前月幼仔对数
    总体对数=本月成兔对数+本月幼仔对数
    可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点,那是:前面相邻两项之和,构成了后一项。

    代码实现:

    public static long isRecursion(int n){
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        if (n > 1)
            return isRecursion(n-1) + isRecursion(n-2);
        else
            return -1;
    }
    

    结果图如下:
    在这里插入图片描述
    八皇后问题:

    问题说明:
    八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法?

    思路分析:
    1.第一个皇后先放第一行第一列
    2.第二个皇后放在第二行第一列,然后判断是否不能相互攻击,如果可以相互攻击,继续放在第二列,第三列,第四列。。。依次把所有的列放完,找到一个合适的
    3.继续放第三个皇后,还是第一列,第二列。。直到第八个皇后也能放在一个不冲突的位置,算是找到一个正确解
    4.在得到正确解时,在栈回退到上一个栈时,就会开始回溯,将第一个皇后放在第一列的所有正确解,全部得到
    5.将第一个皇后放在第二列,循环执行上述步骤

    代码实现:

    public class Queue8 {
        //表示有多少个皇后
         int max = 8;
         static int count=0;  //统计多少种解法
         static int counts=0;   //判断多少次
         //保存皇后放置位置的结果 如0 4 7 5 2 6 1 3  表示第一行第一列(0),第二行第五列(4)..
         //即对应下标表示第几行,arr[i]=val ,val表示第i+1个皇后,放在第i+1行的第val+1列
         int[] arr = new int[max];
         public static void main(String[] args) {
         Queue8 queue = new Queue8();
         queue.check(0);
         System.out.printf("一共有%d种解法",count);
         System.out.printf("一共判断%d次",counts);
    }
         /**
          * 放置第n个皇后
          * @param n
          */
       public void check(int n){
           if(n==max){
                print();
                return;
             }
         for (int i = 0; i <max ; i++) {
             //先把当前的皇后n放到该行第一列
              arr[n]=i;
              //判断是否冲突
              if(isClash(n)){
                  check(n+1);
              }
         }
     }
     /**
     * 放置第n个皇后,是否与前面可以相互攻击
     * @param n  第几个皇后
     * @return
     */
     public boolean isClash(int n){
         counts++;
         for (int i = 0; i < n; i++) {
               //arr[i]==arr[n]判断是否同一列, Math.abs(n-i)==Math.abs(arr[n]-arr[i]判断是否同一斜线
               if(arr[i]==arr[n] || Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
                  return  false;
               }
         }
         return true;
     }
      //输出皇后摆放位置
        public void print(){
            count++;
            for (int i = 0; i <arr.length ; i++) {
                System.out.print(arr[i]+" ");
            }
            System.out.println();
        }
    }
    

    效果图:
    在这里插入图片描述
    可以看出,他要进行1万五千多次判断,效率比较低,后期可以结合一些相应的算法进行优化。著名的递归问题还有很多,汉诺塔,跳台阶。。这里就不举例了。

    展开全文
  • 递归算法

    2020-08-04 14:01:09
    因此,一个正确的递归函数虽然每次调用的是相同的代码,但它的参数、输入数据等均有变化,并且正常情况下随着调用的不断深入必定会出现调用到某一层的函数不再执行递归调用而终止函数的执行,即遇到递归出口。...
  • 函数递归

    2020-12-02 18:57:08
    函数递归 什么是递归 程序调用自身的编程技巧称为递归。递归作为一种算法程序设计语言中广泛应用。一个过程函数其定义或说明中直接或间接调用自身的一种方法,他...*每次递归调用之后越来越接近这个限制条件。 ...
  • 要求将n个圆盘从A移到C,叠放顺序不变,移动过程中遵循下列规则:1 每次只能移动一个圆盘;2 圆盘可三个塔座上任意移动;3 任何时刻,每个塔座上不能将大盘压倒小盘上; 解决方法:* n = 1,直接把圆盘从A...
  • python 实现递归

    2018-05-28 19:20:33
    递归递归就是自己调用自己,(递归一种直接或者简介调用自身的过程) 1:递归就是在过程或函数力调用自身 2:使用递归策率,必须要有一个明确的递归结束条件,称为递归的出口; 3:递归算法解题通常显的很...
  • Java支持递归。递归是根据自身定义内容的过程。就Java编程而言,递归是一个允许方法调用自身的...当每次递归调用返回,将旧的局部变量和参数从堆栈中移除,并将执行控制恢复到方法内部的调用点。递归方法被称为“...
  • 主要思路:每一次调用自己,使用相同的解决问题的方法,但调用的参数每次不同(有规律的变化),使用一个终止处理(结束递归)的条件,当满足这个条件,可得到直接解病能够终止此次递归。 例1: 给定两个...
  • 递归函数

    2017-06-20 17:24:00
     在调用一个函数的过程中,直接或者间接调用函数本身 间接的调用本身 要求:必须要有明确的递归条件 递归函数分成两个阶段 1:递推的往下一层进入,这里每一层都开着等待着 2:回溯 将最后一层...
  • Python之递归

    2017-07-31 18:58:29
    1.递归调用在调用函数过程中,直接或者间接的调用了该函数本身 2.递归的特点: 2.1.递归效率太低 2.2.必须有一个明确的结束条件 2.3.每次进入更深一层递归时,问题规模相比上次递归都应有所减少
  • 参考链接: Python | print()中的结束参数 目录 递归剖析 递归的两个过程 return 返回值 详解 递归思路二分法和递归递归递归练习题 ...直到接触算法后,解决问题,最快,最容易理解的解法就是递归,但是...
  • python-递归

    2017-07-31 15:16:00
    在调用一个函数的过程中,直接或间接使用了函数本身 递归效率很低,需要进入下一次递归时保留当前状态,Python不像其他语言,没有尾递归,但是Python有限制条件,不允许用户无限递归 递归的特点: 1.必须要有一...
  • python之递归

    2018-12-10 11:05:00
    递归:在调用一个函数的过程中,直接或间接地调用了函数本身这个就叫递归 注:Python在递归中没有像别的语言对递归进行优化,所以他的每一次调用都会基于上一次的调用进行,并且他设置了最大的递归数量防止递归外溢 ...
  • 递归

    2012-08-09 16:19:00
    传统递归方法中,每次重复的过程调用都使得调用链条不断加长. 系统不得不使用栈进行数据保存和恢复。如果单项链表十分长,那么上面这个方法就可能会遇到栈溢出,也就是抛出StackOverflowException。这是由于每个...
  • python3 递归

    2017-06-22 23:01:00
    递归调用: 在调用一个函数的过程中,直接或者简介调用了该函数本身  必须有一个明确的结束条件 递归特性: 1. 必须有一个明确的结束条件 2. 每次进入更深一层递归时,问题规模相比上次递归都应有所减少 3. ...
  • 递归输出vector

    2017-03-28 15:07:57
    /* 编写递归输出vector对象的内容,使其有条件地输出执行过程有关的信息。例如,每次调用时输出vector对象的大小,分别打开和关闭调试器的情况下编译并执行这个程序 */
  • Java学习之理解递归

    2017-08-01 22:17:00
    Java支持递归。递归是根据自身定义内容的过程。就Java编程而言,递归是一个允许方法调用自身的特性。调用自身的方法被称为...当每次递归调用返回,将旧的局部变量和参数从堆栈中移除,并将执行控制恢复到方法内部...
  • 递归小叙

    2012-12-06 20:29:30
    一个对自己本身的递归尾调用,就叫做尾递归。这里尾调用的“尾”字,是指运行 需要执行的最后一个动作。不是简单的语法字面上的最后一个语句。...普通的线性递归比尾递归更加消耗资源, 实现上说, 每次重复的过
  • 栈帧空间 : 每次调用函数,内存当中都会单独开辟一个空间,配合函数运行,这个空间叫做栈帧空间 def func(n): print(n,"<===1===>") if n > 0: func(n-1) print(n,"<===2===>") digui(5) ...
  • 递归其实就是一个自己调用自己的过程,起初自己理解递归时总是企图去分析函数调用栈来理解递归过程,一开始简单的递归函数还好分析,但遇到复杂的函数时候分析着分析着就乱套了。因此每次遇到复杂的递归函数...
  • python的递归与二分法

    2019-10-07 10:33:28
    递归:在调用一个函数的过程中,直接或间接地调用了函数本身这个就叫递归 1.必须有个明确的结束条件 2.每次进入更深一层递归时,问题规模相比上次递归应有所减少 3.递归效率不高,递归层次过多会导致栈溢出(...
  • 递归 汉诺塔

    千次阅读 2020-12-08 23:03:53
    内涵数据结构为: 栈(先进后出) 算法思想: 递归调用函数自身) 汉诺塔 (输出移动过程:展示递归) 题目: 经典汉诺塔问题中,有 3 根柱子及 N 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 171
精华内容 68
关键字:

在每次递归过程调用时