while语句

“递归”一节中,我们介绍了用递归求n!的方法,其实每次递归调用都是在重复做同样一件事,就是把n乘到(n-1)!上然后把结果返回。虽说是重复,但每次做都稍微有一点区别(n的值不一样),这种每次都有点区别的重复工作称为迭代(Iteration)。我们使用计算机的主要目的之一就是让它做重复迭代的工作,因为把一件工作重复做成千上万次而不出错正是计算机最擅长的,也是人类最不擅长的。虽然迭代用递归来做就够了,但C语言提供了循环语句使迭代程序写起来更方便。例如factorialwhile语句可以写成:

int factorial(int n)
{
	int result = 1;
	while (n > 0) {
		result = result * n;
		n = n - 1;
	}
	return result;
}

if语句一样,while由一个控制表达式和一个子语句组成,子语句可以是由若干条语句组成的语句块。如果控制表达式的值为真,子语句就被执行,然后再次测试控制表达式的值,如果还是真,就把子语句再执行一遍,再测试控制表达式的值……这种控制流程称为循环(Loop),子语句称为循环体。如果某一次测试控制表达式的值为假,就跳出循环执行后面的return语句,如果第一次测试控制表达式的值就是假,那么直接跳到return语句,循环体一次都不执行。

变量result在这个循环中的作用是累加器(Accumulator),把每次循环的中间结果累积起来,循环结束后得到的累积值就是最终结果,由于这个例子是用乘法来累积的,所以result初值为1,如果是用加法来累积那么result初值应该是0。变量n是循环变量(Loop Variable),每次循环要改变它的值,在控制表达式中要测试它的值,这两点合起来起到控制循环的次数的作用,在这个例子中n的值是递减的,有些循环则采用递增的循环变量。这个例子具有一定的典型性,累加器和循环变量这两种用法在循环中都很常见。

可见,递归能解决的问题用循环也能解决,但解决问题的思路不一样。用递归解决这个问题靠的是递推关系n!=n·(n-1)!,用循环解决这个问题则更像是把这个公式展开了:n!=n·(n-1)·(n-2)·…·3·2·1。把公式展开了理解会更直观一些,所以有些时候循环程序比递归程序更容易理解。但有些时候要把公式展开是非常复杂的甚至是不可能的,反倒是递推关系更直观一些,这种情况下递归程序比循环程序更容易理解。此外还有一点不同:看图 5.2 “factorial(3)的调用过程”,在整个递归调用过程中,虽然分配和释放了很多变量,但是所有的变量都只在初始化时赋值,没有任何变量的值发生过改变,而上面的循环程序则是通过对nresult这两个变量多次赋值来达到同样目的的。前一种思路称为函数式编程(Functional Programming),而后一种思路称为命令式编程(Imperative Programming),这个区别类似于“程序和编程语言”一节讲的Declarative和Imperative的区别。函数式编程的“函数”类似于数学函数的概念,回顾一下“数学函数”一节所讲的,数学函数是没有Side Effect的,而C语言的函数可以有Side Effect,比如在一个函数中修改某个全局变量的值就是一种Side Effect。“局部变量与全局变量”一节指出,全局变量被多次赋值会给调试带来麻烦,如果一个函数体很长,控制流程很复杂,那么局部变量被多次赋值也会有同样的问题。此外,以后我们会讲到,对全局变量多次赋值会影响代码的线程安全性。因此,不要以为“变量可以多次赋值”是天经地义的,很多编程语言都在避免Imperative的方式,例如Erlang语言规定变量的值不允许改变。用C语言编程主要还是采用Imperative的方式,但是要记住,为变量多次赋值时要格外小心,在代码中多次读写同一变量应该以一种一致的方式进行,至于什么才算是“一致的方式”很难定义,也有个人风格的因素,需要读者在编程中自己体会。

正如递归函数如果写得不小心就会变成无穷递归一样,循环如果写得不小心就会变成无限循环(Infinite Loop)或者叫死循环。如果while语句的控制表达式永远为真就是一个死循环,例如while(1){...}。在写循环时要小心检查你写的控制表达式有没有可能取值为假,除非你故意写死循环(有的时候这是必要的)。在上面的例子中,不管n一开始是几,每次循环都会把n减掉1,n越来越小最后必然等于0,所以控制表达式最后必然取值为假,但如果把n = n - 1;那句漏掉就成死循环了。有的时候是不是死循环并不那么一目了然:

while (n != 1) {
	if (n % 2 == 0) {
		n = n / 2;
	} else {
		n = n * 3 + 1;
	}
}

如果n为正整数,这个循环能跳出来吗?循环体所做的事情是:如果n是偶数,就把n除以2,如果n是奇数,就把n乘3加1。一般的循环变量要么递增要么递减,可是这个例子中的n一会儿变大一会儿变小,最终会不会变成1呢?可以找个数试试,例如一开始n等于7,每次循环后n的值依次是:7、22、11、34、17、52、26、13、40、20、10、5、16、8、4、2、1。最后n确实等于1了。读者可以再试几个数都是如此,但无论试多少个数也不能代替证明,这个循环有没有可能对某些正整数n是死循环呢?其实这个例子只是给读者提提兴趣,同时提醒读者写循环时要有意识地检查控制表达式。至于这个循环有没有可能是死循环,这是著名的3x+1问题,目前世界上还无人能证明。许多世界难题都是这样的:描述无比简单,连小学生都能看懂,但证明却无比困难。

习题

1、用循环来解决“递归”一节的练习题,体会递归和循环这两种不同的思路。

2、编写程序数一下1到100的所有整数中出现多少次数字9。在写程序之前先把这些问题考虑清楚:

  1. 这个问题中的循环变量是什么?

  2. 这个问题中的累加器是什么?用加法还是用乘法累积?

  3. 取一个整数的个位和十位在“if/else语句”一节的练习中已经练过了,这两个表达式应该怎样用在程序中?