递归与迭代

由一个问题引出

假设我们要计算 一个正整数的阶乘, N! 。

从数学上看

1！ = 1 
2！ = 2 x 1
3!  = 3 x 2 x 1
4!  = 4 x 3 x 2 x 1
5!  = 5 x 4 x 3 x 2 x 1
:
n! = n x (n-1) x (n-2) x (n-3) x ...  1

我们推出一般公式

f(1) = 1
f(n) =  n  *  f(n-1) ;    n>1

迭代

什么是迭代

迭代的本质就是循环，利用循环对变量进行值的迭代(更新)。

迭代思想

迭代代码实现

public int f(int n){int s = 1;for(int i = 2; i <=n;i++){s = s * i;}return s;
}

递归

什么是递归

从本质上说：从本质上，将原来的问题转化为更小的同一问题

递归从计算机角度看

先压入我们要的问题，依次压入它相似的小问题解，直到找不到再小的解，那么将结果按照LIFO方式推出。

递归基本思路

递归代码

LCR 136. 删除链表的节点 - 力扣（LeetCode）

public int f(int n){if(n==1) return 1;return n * f(n-1);
}

---

链表与递归

遍历链表

迭代法

  ListNode curr = head;while(curr!=null){System.out.print(curr.val+"\t");}

递归法

public void traversal(ListNode head){if(head == null) return;System.out.println(head.val+"\t");traversal(head.next);
}

使用递归进行链表节点删除

算法核心

递归查找到最后一个节点入栈，待出栈过程中（递归调用）判断是否是需要删除的节点。

• 找到节点返回下一个节点
• 连接下个节点，返回节点

class Solution {public ListNode deleteNode(ListNode head, int val) {if(head == null){return null;}ListNode result = deleteNode(head.next, val);if(head.val == val){return result;}else{head.next = result;return head;}}
}