你的位置:首页 > Java教程

[Java教程]递归的相关概念


  几天没有更新,这两天是周末,给大家整理了一几篇东西,有关于作用域的,闭包的,还有递归的,闭包和递归,对于大部分初次接触编程的人来说还是有些难度的,昨天,花了一点时间给大家整理了一下,今天,给大家上传上来,让大家看看,部分属于个人观点,如有错误,欢迎指出

  这一篇,给大家讲讲递归,昨天整理着三篇文章花了点时间,查了点资料,把自己的理解和大家说说,但是很多我也讲的不是很清楚,所以这一篇当中会用很多的小例子,小练习,给大家说说,希望可以给大家讲讲清楚。

1. 递归

1.1. 什么是递归

在程序中,所谓的递归,就是函数自己直接或者间接的调用自己

  1. 直接调用自己
  2. 间接调用自己

就递归而言最重要的就是跳出结构,因为跳出了才可以有结果

1.2. 所谓的递归就是化归思想

递归的调用,写递归函数,最终还是要转换为自己这个函数

假如有一个函数f,如果它是递归函数,那么也就是说函数体内的问题还是转换为f的形式

递归思想就是将一个问题转换为一个已解决的问题来实现

  function f(){    ...f(...)...  }

例子: 1, 2, 3, 4, 5, ..., 100

  1. 首先假定递归函数已经写好, 假设是 foo. 即 foo( 100 ) 就是求 1 到 100 的和
  2. 寻找递推关系. 就是 n 与 n-1, 或 n-2 之间的关系: foo( n ) == n + foo( n - 1 )
     var res = foo( 100 ); var res = foo( 99 ) + 100;
  3. 将递推结构转换为 递归体
     function foo( n ) {   return n + foo( n - 1 ); }
    • 将 求 100 转换为 求 99
    • 将 求 99 转换为 求 98
    • ...
    • 将求 2 转换为 求 1
    • 求 1 结果就是 1
    • 即: foo( 1 ) 是 1
  4. 将临界条件加到递归体中
     function foo( n ) {   if ( n == 1 ) return 1;   return n + foo( n - 1 ); }

练习: 求 1, 3, 5, 7, 9, ... 第 n 项的结果与前 n 项和. 序号从 0 开始

求第 n 项的

  1. 首先假定递归函数已经写好, 假设是 fn. 那么 第 n 项就是 fn( n )
  2. 找递推关系: fn( n ) == f( n - 1 ) + 2
  3. 递归体
     function fn( n ) {   return fn( n-1 ) + 2; }
  4. 找临界条件
    • 求 n -> n-1
    • 求 n-1 -> n-2
    • ...
    • 求 1 -> 0
    • 求 第 0 项, 就是 1
  5. 加入临界条件
     function fn( n ) {   if ( n == 0 ) return 1;   return fn( n-1 ) + 2; }

前n项和

  1. 假设已完成, sum( n ) 就是前 n 项和
  2. 找递推关系: 前 n 项和 等于 第 n 项 + 前 n-1 项的和
  3. 得到递归体
     function sum( n ) {   return fn( n ) + sum( n - 1 ); }
  4. 找临界条件
    • n == 1 结果为 1
  5. 得到递归函数
     function sum( n ) {   if ( n == 0 ) return 1;   return fn( n ) + sum( n - 1 ); }

练习: 2, 4, 6, 8, 10 第 n 项与 前 n 项和

第n项

function fn( n ) {  if ( n == 0 ) return 2;  return fn( n-1 ) + 2;}

前n项和

function sum( n ) {  if ( n == 0 ) return 2;  return sum( n - 1 ) + fn( n );}

练习: 数列: 1, 1, 2, 4, 7, 11, 16, … 求 第 n 项, 求前 n 项和.

求第 n 项

  1. 假设已经得到结果 fn, fn( 10 ) 就是第 10 项
  2. 找递推关系
    • 0, 1 => fn( 0 ) + 0 = fn( 1 )
    • 1, 2 => fn( 1 ) + 1 = fn( 2 )
    • 2, 3 => fn( 2 ) + 2 = fn( 3 )
    • ...
    • n-1, n => fn( n-1 ) + n - 1 = fn( n )
  3. 递归体也就清楚了, 临界条件是 n == 0 => 1
     function fn( n ) {   if ( n == 0 ) return 1;   return fn( n-1 ) + n - 1; }

如果从 1 开始表示, 那么第 n 项为

  1. 假设已经得到结果 fn, fn( 10 ) 就是第 10 项
  2. 找递推关系
    • 1, 2 => fn( 1 ) + 0 = fn( 2 )
    • 2, 3 => fn( 2 ) + 1 = fn( 3 )
    • 3, 4 => fn( 3 ) + 2 = fn( 4 )
    • ...
    • n-1, n => fn( n-1 ) + n - 2 = fn( n )
  3. 临界条件 n == 1 => 1

前n项和

  function sum( n ) {    if ( n == 0 ) return 1;    return sum( n - 1 ) + fn( n );  }

如果从 0 开始

0 1 2 3 4 5  61, 1, 2, 4, 7, 11, 16,

如果从 1 开始

1 2 3 4 5 6  71, 1, 2, 4, 7, 11, 16,

练习: Fibonacci 数列: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … 求其第 n 项.

递推关系 fn(n) == fn( n- 1) + fn( n - 2)

  function fib( n ) {    if ( n == 0 || n == 1 ) return 1;    return fib( n - 1 ) + fib( n - 2 );  }

1.3. 高级递归练习

1.3.1. 阶乘

阶乘是一个运算, 一个数字的阶乘表示的是从 1 开始 累乘到这个数字. 例如 3! 表示 1 * 2 * 3. 5! 就是 1 * 2 * 3 * 4 * 5. 规定 0 没有阶乘, 阶乘 从 1 开始.

求 n 的阶乘

  function foo ( n ) {    if ( n == 1 ) return 1;    return foo( n - 1 ) * n;  }

1.3.2. 求幂

求幂就是求 某一个数 几次方

2*2 2 的 平方, 2 的 2 次方

求 n 的 m 次方

最终要得到一个函数 power( n, m )

n 的 m 次方就是 m 个 n 相乘 即 n 乘以 (m-1) 个 n 相乘

  function power ( n, m ) {    if ( m == 1 ) return n;    return power( n, m - 1 ) * n;  }

1.3.3. 深拷贝

可能还有些人不知道什么是深拷贝,深拷贝对应的是浅拷贝

  1. 什么是深拷贝, 什么是浅拷贝
    • 如果拷贝的时候, 将数据的所有引用结构都拷贝一份, 那么数据在内存中独立就是深拷贝
    • 如果拷贝的时候, 只针对当前对象的属性进行拷贝, 而属性是引用类型这个不考虑, 那么就是浅拷贝
    • 拷贝: 复制一份. 指将对象数据复制.
    • 在讨论深拷与浅拷的时候一定要保证对象的属性也是引用类型.
  2. 代码的封装
    • 利用面向对象的思想, 一般会让对象带有一个 copy 的方法, 来完成自己的拷贝
    • 如果需要将一个对象封装成浅拷贝
    • this 在函数( 方法 )内部, 表示调用该函数( 方法 )的对象.

如果要实现深拷贝那么就需要考虑将对象的属性, 与属性的属性, ... 都拷贝过来

如果要实现:

  1. 假设已经实现clone(o1,o2),将对象o2的成员拷贝一份交给o1
  2. 简单的算法,将o2的属相拷贝到o1中去
  function clone( o1, o2 ) {    for ( var k in o2 ) {      o1[ k ] = o2[ k ];    }  }
  1. 找递推关系,或叫化归为已经解决的问题

    • 假设方法已经实现,问一下,如果o2[k]是对象
    • 继续使用这个方法
    • 因此需要考虑的是o2[k]如果是引用类型,再使用一次clone()函数
    • 如果o2[k]不是引用类型,那么就直接赋值
      function clone( o1, o2 ) { for ( var k in o2 ) {   if ( typeof o2[ k ] == 'object' ) {     o1[ k ] = {};     clone( o1[ k ] , o2[ k ] );   } else {     o1[ k ] = o2[ k ];   } }}

    复杂实现:clone(o) -> newObj

  function clone( o ) {    var temp = {};    for ( var k in o ) {      if ( typeof o[ k ] == 'object' ) {        temp[ k ] = clone( o[ k ] );      } else {        temp[ k ] = o[ k ];      }    }    return temp;  }

请用 递归实现 getElementsByClassName

<div>  <div>1    <div >2</div>    <div>3</div>  </div>  <div >4</div>  <div>5    <div>6</div>    <div >7</div>  </div>  <div>8</div></div>
  1. 如果实现一个方法byClass(node,"c",list),表示在某一个节点上查找符合class属性为c的元素
  2. 在当前元素的子元素中查找,如果有符合要求的,存储到一个数组中
  3. 首先遍历子节点,然后看子节点是否还有子节点,如果没有直接判断,如果有再递归
  function byClass( node, className, list ) {    var arr = node.childNodes;    for ( var i = 0; i < arr.length; i++ ) {      if ( arr[ i ].className == className ) {        list.push( arr[ i ] );      }      if ( arr[ i ].childNodes.length > 0 ) {        byClass( arr[ i ], className, list );      }    }  }