使用 C 的 DSA - 递归

概述

递归是指编程语言中的一种技术,其中函数调用自身。调用自身的函数称为递归方法。

特征

递归函数必须具备以下两个特征。

  • 基本情况

  • 在减少情况后导致基本情况的规则集。

递归阶乘

阶乘是递归的经典示例之一。阶乘是满足以下条件的非负数。

  • 0!= 1

  • 1!= 1

  • n! = n * n-1!

阶乘用"!"表示。这里规则 1 和规则 2 是基本情况,规则 3 是阶乘规则。

例如,3! = 3 x 2 x 1 = 6

int factorial(int n){
   //base case
   if(n == 0){
      return 1;
   } else {
      return n * factorial(n-1);
   }
}
阶乘调用跟踪

递归斐波那契数列

斐波那契数列是递归的另一个经典示例。斐波那契数列是满足以下条件的一系列整数。

  • F0 = 0

  • F1 = 1

  • Fn = Fn-1 + Fn-2

斐波那契用"F"表示。这里规则 1 和规则 2 是基本情况,规则 3 是斐波那契规则。

例如,F5 = 0 1 1 2 3

示例

#include <stdio.h>

int factorial(int n){
   //base case
   if(n == 0){
      return 1;
   } else {
      return n * factorial(n-1);
   }
}
int fibbonacci(int n){
   if(n ==0){
      return 0;
   }
   else if(n==1){
      return 1;
   } else {
      return (fibbonacci(n-1) + fibbonacci(n-2));
   }
}
main(){
   int n = 5;
   int i;
   printf("Factorial of %d: %d
" , n , factorial(n));
   printf("Fibbonacci of %d: " , n);
   for(i=0;i<n;i++){
      printf("%d ",fibbonacci(i));            
   }
}

输出

如果我们编译并运行上述程序,则会产生以下输出 −

Factorial of 5: 120
Fibbonacci of 5: 0 1 1 2 3