基本算法连载（11）－两个基本概念：in-place和tail-end recursion

平时看算法，经常碰到in-place algorithm和tail-end recursion两个概念。今天终于了解了这两个概念。
In-place算法：The input is usually overwritten by the output as the algorithm executes.函数语言是不鼓励或支持in-place算法的，它把overwriiten当作side effect。函数语言，听过不少，没有学过，有时间得学学。
代码：

int sum(int n){
int i;
int sum = 0;
for(i=1;i<=n;i++){
sum = sum+i;
}
return sum;
}

此处的sum就被overwritten，可以算作in-place算法。

Tail-end recursion(tail recursion)：函数所做的最后一件事情是一个函数调用，被称作尾部调用（tail－call）。使用尾部调用的递归程序称为尾部递归。tail-recursion是很容易转变成iteration的。在把尾部递归程序转变成非递归程序时，我们就有了理论保证。尾部调用是可以进行优化的：在尾部进行函数调用时使用一个栈结构覆盖当前的栈结构，同时保持原来的返回地址。
以下的代码展示的是一个更一般化的tail recursion，它先转变成熟悉的tail recursion，然后转变成iteration。看惯了Java代码，看这个还有点不习惯。
代码：

#include <stdlib.h>
typedef struct list{
 int value;
 struct list* next;
}list;

//----------------------------------
//一般化的tail-recursion
list* f(list* input){
 list* head;
 if(input == NULL){
  head = NULL;
 }else{
  head = (list*)malloc(sizeof(list));
  head->value = input->value;
  head->next = f(input->next);
 }
 return head;
}

//------------------------------------
//熟悉的tail-recursion
void fprime(list* input,list** p){
 if(input == NULL){
  *p = NULL;
 }else{
  *p = malloc(sizeof(list));
  (*p)->value = input->value;
  fprime(input->next,&(*p)->next);
 }
}

list* f1(list* input){
 list* head;
 fprime(input,&head);
 return head;
}

//------------------------------------
//iteration
list* f2(list*input){
 list* head;
 list** p;
 p = &head;
 while(input != NULL){
  *p = (list*)malloc(sizeof(list));
  (*p)->value = input->value;
  input = input->next;
  p = &(*p)->next;
 }
 *p = NULL;
 return head;
}