一些基本算法的递归实现

65 阅读 0 评论 43 点赞

我是靠谱客的博主粗心信封，最近开发中收集的这篇文章主要介绍一些基本算法的递归实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述：

递归是计算机科学中最伟大的思想。按照我的理解，所谓递归就是把问题化约为比自身维度更小的问题，直至边界点（base condition)，

然后利用边界点的解的结果（相对容易得到）和一定规则回退得到最终所需要的结果。

常用到的递归思想的可归类为：

1. 各种tree construct 的操作：遍历（inorder, preorder, postorder)，深度优先搜索（dfs)，广度优先搜索（bfs)，插入，删除，返回最值等；

2. 各种搜索问题最终都能化约为递归问题。比如八皇后，排列，组合，背包等等；

3. 下面我尝试用递归思想实现一些平时最常用的操作（比如加法，乘法等）：

代码如下：

[cpp] 
view plain
copy

 int max( int a, int  b )  
 {  
     if( a  > b )  
         return a;  
       
     return b;  
 }  
   
 int min( int a, int b )  
 {  
     if( a < b )  
         return a;  
       
     return b;  
 }  
   
 int Add( int m, int n )  
 {  
     if( 0 == n )  
         return 0;  
       
     return Add( m + 1, n - 1);  
 }  
   
 int Mutiple( int m, int n )  
 {  
     if( 1 == n )  
     {  
         return m;  
     }  
       
     return Mutiple( m + m, n - 1 )  
 }  
   
 int Subtract( int m, int n )  
 {  
     if( 0 == n )  
     {  
         return 0;  
     }  
       
     return Subtract( m - 1, n - 1 );  
 }  
   
 int findMax( int* items, int idx, int size )  
 {  
     if( idx == size - 1)  
         return items[idx];  
       
     return max(  findMax( items, idx + 1, size ), items[idx] );  
 }  
   
 int findMin( int* items, int idx, int size )  
 {  
     if( idx == size - 1 )  
         return items[idx];  
       
     return min( findMin( items, idx + 1, size ), items[idx] );  
 }  
   
 int Search( int* items, int idx, int size, int val )  
 {  
     if( idx >= size )  
         return -1;  
       
     if( items[idx] == val )  
         return idx;  
       
     return Search( items, idx + 1, size, val );  
 }  
   
 int BinarySearch( int* items, int begin, int end, int val )  
 {  
     if( begin > end )  
         return -1;  
       
     int mid = begin + ( ( end - begin ) >> 1 );  
     if( items[mid] > val )  
     {  
         return BinarySearch( items, begin, mid - 1, val );  
     }  
     else if( items[mi] < val )  
     {  
         return BinarySearch( items, mid + 1, end, val );  
     }  
     else  
     {  
         return mid;  
     }  
 }  
   
 int gcd( int n, int m )  
 {  
     if( 0 == m )  
         return n;  
       
     return gcd( m, n % m );  
 }  
   
 int fibonical( int n )  
 {  
     if( 1  == n )  
         return 1;  
       
     return fibonical( n - 1 ) + fibonical( n - 2 );  
 }  
   
 int fictional( int n )  
 {  
     if( 1 == n )  
         return n;  
       
     return n * fictional( n - 1 );  
 }  
   
 unsigned int power( int n, int m )  
 {  
     if( 1 == m )  
         return n;  
       
     return power( n * m, m - 1 );  
 }  
   
   
 unsigned int powerQuick( int n, int m )  
 {  
     if( 1 == m )  
         return n;  
       
     unsigned int k = powerQuick( n, m / 2 );  
       
     if( 0 == m % 2 )  
     {  
         return k * k;  
     }  
     else  
     {  
         return k * k * powerQuick( n, 1 );  
     }  
       
 }  
   
   
   
 unsigned int Fib( int n, unsigned int a, unsigned int b )  
 {  
     if( 1 == n )  
         return b;  
       
     return Fib( n - 1, b, a + b );  
 }  
   
   
 void EulerLetter( int n, int depth, int* result )  
 {  
     if( depth == n )  
     {  
         for( int i = 0; i < dpeth; i++ )  
         {  
             printf( "%d ", result[i] );  
         }  
           
         printf( "n" );  
       
         return;  
     }  
       
       
     for( int i = 0; i < n; i++ )  
     {  
         if( depth != i )  
         {  
             result[depth] = i;  
             EulerLetter( n, depth + 1, result );  
         }  
     }  
 }  