Cprogramming 简明教程

Recursion in C

Recursion 是一个函数调用自身的过程。C 语言允许编写将自身调用以通过将复杂问题分解为简单易解的问题来解决问题的函数。这些函数被称为 recursive functions 。

Recursion is the process by which a function calls itself. C language allows writing of such functions which call itself to solve complicated problems by breaking them down into simple and easy problems. These functions are known as recursive functions.

What is a Recursive Function in C?

C 中的递归函数是一个 function ，它调用自身。当某个问题以其自身术语定义时，就会使用递归函数。尽管它涉及到迭代，但使用迭代方法来解决此类问题可能会很乏味。递归方法为看似复杂的问题提供了非常简洁的解决方案。

A recursive function in C is a function that calls itself. A recursive function is used when a certain problem is defined in terms of itself. Although it involves iteration, using iterative approach to solve such problems can be tedious. Recursive approach provides a very concise solution to seemingly complex problems.

Syntax

一般的递归函数如下所示 −

This is how a general recursive function looks like −

void recursive_function(){
   recursion();   // function calls itself
}

int main(){
   recursive_function();
}

在使用递归时，程序员需要小心地定义函数的退出条件，否则它将进入 infinite loop 。

While using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.

Why Recursion is Used in C?

递归用于执行复杂任务，例如 tree 和 graph 结构遍历。常见的递归编程解决方案包括阶乘、二分查找、树遍历、汉诺塔、国际象棋中的八皇后问题等。

Recursion is used to perform complex tasks such as tree and graph structure traversals. Popular recursive programming solutions include factorial, binary search, tree traversal, tower of Hanoi, eight queens problem in chess, etc.

递归程序虽然简洁，但不容易理解。即使代码的大小可能减少，但它需要更多的处理器资源，因为它涉及对函数的多个 IO 调用。

A recursive program becomes concise, it is not easily comprehendible. Even if the size of the code may reduce, it needs more resources of the processor, as it involves multiple IO calls to the function.

Factorial Using Recursion

递归函数对于解决许多数学问题非常有用，例如计算某个数的阶乘、生成斐波那契数列等。

Recursive functions are very useful to solve many mathematical problems such as calculating the factorial of a number, generating Fibonacci series, etc.

递归最常见的例子是阶乘的计算。在数学上，阶乘的定义如下：

The most popular example of recursion is calculation of factorial. Mathematically, a factorial is defined as −

n! = n X (n-1)!

可以看出，我们使用阶乘本身来定义阶乘。因此，这是一个编写递归函数的合适案例。让我们展开上述定义以计算 5 的阶乘值。

It can be seen that we use factorial itself to define factorial. Hence this is a fit case to write a recursive function. Let us expand the above definition for calculating the factorial value of 5.

5! = 5 X 4!
   5 X 4 X 3!
   5 X 4 X 3 X 2!
   5 X 4 X 3 X  2 X 1!
   5 X 4 X 3 X  2 X 1
   = 120

虽然我们可以使用循环执行此计算，但其递归函数涉及通过递减数字依次调用它，直到数字变为 1。

While we can perform this calculation using a loop, its recursive function involves successively calling it by decrementing the number till it reaches 1.

Example: Non-Recursive Factorial Function

以下程序演示了如何使用非递归函数来计算一个数字的阶乘：

The following program shows how you can use a non-recursive function to calculate the factorial of a number −

#include <stdio.h>
#include <math.h>

// function declaration
int factorial(int);

int main(){
   int a = 5;
   int f = factorial(a);

   printf("a: %d \n", a);
   printf("Factorial of a: %d", f);
}
int factorial(int x){
   int i;
   int f = 1;

   for (i = 5; i >= 1; i--){
      f *= i;
   }
   return f;
}

Output

当你运行这段代码时，它将产生以下输出：

When you run this code, it will produce the following output −

a: 5
Factorial of a: 120

Example: Recursive Factorial Function

现在让我们编写一个递归函数来计算给定数字的阶乘。

Let us now write a recursive function for calculating the factorial of a given number.

以下示例使用递归函数计算给定数字的阶乘：

The following example calculates the factorial of a given number using a recursive function −

#include <stdio.h>
#include <math.h>

/* function declaration */
int factorial(int i){

   if(i <= 1){
      return 1;
   }
   return i * factorial(i - 1);
}
int main(){
   int a = 5;
   int f = factorial(a);

   printf("a: %d \n", a);
   printf("Factorial of a: %d", f);
   return 0;
}

Output

运行代码并检查其输出：

Run the code and check its output −

a: 5
Factorial of a: 120

当 main() 函数通过传递变量 "a" 来调用 factorial() 函数时，其值存储在 "i" 中。factorial() 函数依次调用自身。

When the main() function calls the factorial() function by passing the variable "a", its value is stored in "i". The factorial() function successively calls itself.

在每次调用中，“i” 的值都会乘以其较早的值，然后减 1，直到达到 1。当它达到 1 时，参数初始值与 1 之间所有值的乘积将返回给 main() 函数。

In each call, the value of "i" is multiplied by its earlier value after reducing it by 1, till it reaches 1. As it reaches 1, the product of all the values between the initial value of the argument and 1 is returned to the main() function.

Binary Search Using Recursion

让我们看另一个示例来了解递归的工作原理。手头的问题是检查给定的数字是否存在于｛@s0｝中。

Let us have a look at another example to understand how recursion works. The problem at hand is to check whether a given number is present in an array.

虽然我们可以使用｛@s3｝对列表中的某个数字执行｛@s2｝并比较每个数字，但是顺序搜索效率低下，尤其是当列表过长时。

While we can perform a sequential search for a certain number in the list using a for loop and comparing each number, the sequential search is not efficient, especially if the list is too long.

｛@s4｝检查索引 "start" 是否大于索引 "end"。根据变量 "mid" 中存在的值，再次调用该函数以搜索元素。

The binary search algorithm checks if the index "start" is greater than the index "end". Based on the value present at the variable "mid", the function is called again to search for the element.

我们有一个按升序排列的数字列表。然后，我们找到列表的中点，并将检查限制在中点的左侧或右侧，具体取决于所需数字小于还是大于中点的数字。

We have a list of numbers arranged in ascending order. Then we find the midpoint of the list and restrict the checking to either left or right of the midpoint, depending on whether the desired number is less than or greater than the number at the midpoint.

Example: Recursive Binary Search

以下代码实现了递归二分查找技术 -

The following code implements the recursive binary searching technique −

#include <stdio.h>

int bSearch(int array[], int start, int end, int element){

   if (end >= start){

      int mid = start + (end - start ) / 2;

      if (array[mid] == element)
         return mid;

      if (array[mid] > element)
         return bSearch(array, start, mid-1, element);
         return bSearch(array, mid+1, end, element);
   }
   return -1;
}

int main(void){
   int array[] = {5, 12, 23, 45, 	49, 67, 71, 77, 82};
   int n = 9;
   int element = 67;
   int index = bSearch(array, 0, n-1, element);

   if(index == -1 ){
      printf("Element not found in the array ");
   }
   else{
      printf("Element found at index: %d", index);
   }
   return 0;
}

运行代码并检查其输出：

Run the code and check its output −

Element found at index: 5

Fibonacci Series Using Recursion

在斐波那契数列中，一个数字是其前两个数字的和。要生成斐波那契数列，第 i 个数字是 i-1 和 i-2 的和。

In Fibonacci series, a number is the sum of its previous two numbers. To generate Fibonacci series, the ith number is the addition of i−1 and i−2.

Example

以下示例使用递归函数为给定的数字生成斐波那契数列中的前 10 个数字：

The following example generates the first 10 numbers in the Fibonacci series for a given number using a recursive function −

#include <stdio.h>

int fibonacci(int i){

   if(i == 0){
      return 0;
   }

   if(i == 1){
      return 1;
   }
   return fibonacci(i-1) + fibonacci(i-2);
}

int main(){

   int i;

   for (i = 0; i < 10; i++){

      printf("%d\t\n", fibonacci(i));

   }
   return 0;
}

编译并执行上述代码后，将产生以下结果 −

When the above code is compiled and executed, it produces the following result −

初学者难以在程序中实现递归。虽然任何迭代过程都可以转换为一个递归过程，但并非所有递归情况都可以轻松地以迭代方式表示。

Implementing recursion in a program is difficult for beginners. While any iterative process can be converted in a recursive process, not all cases of recursion can be easily expressed iteratively.