Fork me on GitHub

算法———递归算法

发表于 | 分类于 | |
  • 递归函数的调用，本质就是函数调用

数组求和递归解读

1
2
3
4
5
6
public static int sum(int[] arr,int l)
{
	if(l == arr.length)
		return 0;
	return arr[l] + sum(arr,l+1)
}
1
2
3
4
5
6
7
8
public static int sum(int[] arr,int l)
{
	if(l == arr.length)
		return 0;
	int x = sum(arr,l+1);
	int res = arr[l] + x;
	return res;
}

递归分析

  1. 数组 arr = [6,10],调用sum（arr,0）,l=0,进入第二句，int x = sum(arr,l+1),进入步骤2，这时l+1；
  2. 调用sum（arr,1），l=1,进入第二句，int x = sum(arr,l+1),进入步骤3，这时l+1；
  3. 调用sum（arr,2）,l=2,返回0；返回步骤2继续执行；
  4. int res = arr[l]+x; l = 1,arr[1] = 10,res=10,返回res，继续执行步骤1；
  5. int res = arr[l]+x，l = 0,arr[0] = 6,res=16,返回res，执行完毕。

链表递归解读

1
2
3
4
5
6
7
8
9
10
public Listpublic class Solution
{
    public ListNode removeElements(ListNode head, int val)
    {
       1 if(head == null)
            return null;
       2 head.next = removeElements(head.next,val);
       3 return head.val == val? head.next:head;
    }
}

  1. 对链表6->7->8->null调用，执行语句1，不为空，执行语句2，head.next = ?，调用函数removeElements(head.next,val)，执行步骤2；
  2. 对链表7->8->null调用，执行语句1，不为空，执行语句2, head.next = ?,调用函数removeElements(head.next,val)，执行步骤3；
  3. 对链表8->null调用，执行语句1，不为空，执行语句2，head.next = ?调用函数removeElements(head.next,val)，执行步骤4；
  4. head.next = null,执行语句3，不是7，返回null，执行步骤3；
  5. head.next=null,执行语句3，返回8->null，执行步骤2;
  6. head.next=8->null，这时链表为7->8->null,执行语句3，是7，删除返回8->null，执行步骤1；
  7. head.next=8->null,这时链表为6->8->null,执行完毕。
  • 程序调用的系统栈
  • 递归调用代价：函数调用+系统栈空间