黑马程序员技术交流社区

标题: 方法的递归调用 [打印本页]
作者: qdwyuotg    时间: 2013-7-12 10:07
标题: 方法的递归调用
最近正在基础加强，有关方法的递归调用，在确定临界条件上有点晕，大家有没有一些好的技巧可以分享的？特别是在多层调用的情况？
作者: 许大虾    时间: 2013-7-12 10:12
给你个例子呗  http://blog.sina.com.cn/s/blog_6ef263e20100lp5h.html
作者: zhangcheng5468    时间: 2013-7-12 10:46
在C#语言中，除了Main方法以外的所有方法都允许调用其他方法或被其他方法调用，也可以调用本身。方法的递归调用即方法调用自身。

  下面是递归调用实现昂纳多.斐波那契通过兔子的繁殖来引入这样一个数列：1，1,2,3,5,8,13。。。。。。








using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication17
{
    class Program
    {
        static void Main(string[] args)//主方法程序入口
        {
            Console.WriteLine("请输入数列长度：");//提示用户输入数列长度
            long n = long.Parse(Console.ReadLine());//输入数列长度
            Console.WriteLine(fibonacci(n));//调用下面写好的方法
            Console.ReadKey();//等待用户输入
        }
        static long fibonacci(long n)//求递归的方法
        {
            if (n == 1 || n == 2)//判断数值
                return 1;//当n=0或者1时，值为1
            else
            {
                return fibonacci(n - 1) + fibonacci(n - 2);//调用该方法本身，实现递归调用
            }
        }
    }
}
就这么简单！

作者: 聂广强    时间: 2013-7-12 11:05
递归简单的说就是 自己调用自己 在递归中最多也只能调用40次左右 再多的话耗时会翻倍增加 要是能有一百次的调用的话 放心 这辈子都不会见到结果了

给你一段代码是 斐波那契数列：0、1、1、2、3、5、8、13、21、.。。。求第30个数的方法 这个是我在面试的时候遇到的一个面试 题
  1. public class MainTest
  2. {
  3.       public static void Main()
  4. {
  5.      Console.WriteLine(Fun(30));
  6. }
  7. public static intFun(int i)
  8. {
  9.       if (i <= 0)
  10.     return 0;
  11.     else if(i > 0 && i <= 2)
  12.     return 1;
  13.     else return Fun(i -1) + Fun(i - 2);
  14. }
  15. }
复制代码
作者: qdwyuotg    时间: 2013-7-12 11:20
首先谢谢大家的回贴！
我目前在职，方法的递归调用在工作中用的还挺多的，有时非常方便。
最近在想，方法的递归调用，其临界条件的确定有没有一些技巧或原则可寻，大家有没有一些好的建议可以分享的...
作者: 彭家贰小姐    时间: 2013-7-12 14:54
最重要的是 防止死循环
作者: sxdxgzr@126.com    时间: 2013-7-16 22:37

递归： 若果原问题的规模为n，那递归的思想就是将规模缩小，也就是说规模为n问题的解依赖于规模为n-1的问题的解，这样重复下去，一直到较小规模的问题可以直接求解，利用求得的解层层返回，最终得出问题规模为n的解。
         这就可以看出规模为n的问题和规模为n-1的问题之间存在关系 可以列出方程(n>=N1>0)  
         当n<N1这个部分就是问题规模最小的部分也就是临界条件，这个时候是可以直接求解的。
eg:1求n的阶乘 很容易看出当n=0或n=1时候 n!=1这部分能直接求解    而n>1 时候 f(n)=n*f(n-1)有这样的关系方程。

总而言之：确定临界条件关键是找出能直接求解的规模最小(N1)的问题，(此问题(N1)与规模为N的问题同类型 仅是规模大小不同而已。) 如二叉树递归遍历算法 空树就是临界条件。

下面是个人对递归的理解：

递归：（是一种分析、解决问题的思想）
递归的基本概念：
      1了解分治的思想：将一个难以解决的大问题分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可以分割成k个子问题，1<k<=n,且这些子问题都是可以解决的，并利用这些子问题的解求出原问题的解，那么这种分支方法就是可行的。
      2分治法产生的子问题往往是原问题的较小模式，在这种情况下反复使用分支手段，使子问题与原问题类型一致而起规模不断缩小，最终使子问题能够较为简单的求解。然后利用这些子问题的解最终解决原问题（这是因为原问题在分治过程中始终是依赖于子问题的，它们之间就满足一定的关系）。这样自然就产生了递归算法。
      3个人认为分治思想的上述2就是递归思想的精要描述。我们在考虑是否使用递归是由上述2得出两个方面：一是，考虑原问题是否能够划分为一些子问题求解，这些子问题是否与原问题类型一致而规模缩小。2找较小问题的解（即递归的终止条件）。
     4找出原问题与子问题的关系，并建立递归方程（可以使用数学语言将其描述清楚），同时找出递归方程的初始化条件以及各个变量的约束条件。

递归算法：间接或直接调用自身的算法。这个过程就要依赖于递归方程。


递归实现的基本原理：
       采用栈的工作机制来实现。因为我们发现在程序递归调用的过程中需要保存当前调用的信息为上层调用多用，二且这种调用也满足先进后出原则。只有当前下层调用完成后，当前调用才能退栈。这个我们以前学过的N!采用递归实现时就建立了一系列的工作栈，通过0！=1然后层层返回值，从而层层退栈，最终解决n!问题。不过最为经典的还是汉诺塔问题。



递归解决策略：个人认为非常关键的在于通过原问题分析得出的子问题也和原问题类型一致（否则不能使用递归而应使用分治），再进行抽象总结出子问题和当前原文题的关系从而抽象出动归方程，最后弄清楚递归终止条件和约束关系。最终可依此编写出相应的算法。

递归的分析案例：
       二叉树的先序递归遍历：
       我们知道二叉树的定义就是一个递归定义，意味着不需要分析就可以使用递归方程。因为当二叉树有n>1个节点时，它的子树也是一颗二叉树，那么毫无疑问遍历二叉树的操作与遍历二叉树子树的操作是一样的。最小的二叉树就是一个结点它的左子树与右子树都为空，访问该结点遍历结束，于是得到了遍历二叉树的终止条件。
当前二叉树不为空时：
      1遍历当前二叉树的根节点
      2先序遍历该二叉树左子树
      3先序遍历该二叉树右子树




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2