Why? The recursion may end up being quite deep, and because of practical stack size limitations, the approach may limit you to very small mazes. Your example maze is only 7×7, giving a the maximum recursion depth is 49, which is still safe.
When writing recursive functions, you really should print the state at each recursive call, to see exactly the changes each function does.
I wrote a 222-line example program to find out if there are any potholes in the recursive solution. Here is what my program outputs for me:
Code:
1 0 0 0 0 0 0 1. check() call.
64 0 0 64 64 64 0
64 0 0 64 0 64 0
64 64 64 64 0 64 0
0 64 0 0 0 64 0
0 64 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 2. check() call, called by 1.
2 0 0 64 64 64 0
64 0 0 64 0 64 0
64 64 64 64 0 64 0
0 64 0 0 0 64 0
0 64 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 3. check() call, called by 2.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
64 64 64 64 0 64 0
0 64 0 0 0 64 0
0 64 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 4. check() call, called by 2.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
64 64 64 64 0 64 0
0 64 0 0 0 64 0
0 64 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 5. check() call, called by 4.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 64 64 64 0 64 0
0 64 0 0 0 64 0
0 64 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 6. check() call, called by 4.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 64 64 64 0 64 0
0 64 0 0 0 64 0
0 64 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 7. check() call, called by 6.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 64 0 0 0 64 0
0 64 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 8. check() call, called by 6.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 64 0 0 0 64 0
0 64 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 9. check() call, called by 8.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 6 0 0 0 64 0
0 64 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 10. check() call, called by 8.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 6 0 0 0 64 0
0 64 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 11. check() call, called by 10.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 12. check() call, called by 10.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 64 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 13. check() call, called by 12.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 14. check() call, called by 12.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
64 64 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 15. check() call, called by 14.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
64 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 16. check() call, called by 14.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
64 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 17. check() call, called by 16.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 18. check() call, called by 6.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 64 64 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 19. check() call, called by 18.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 6 64 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 20. check() call, called by 18.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 6 64 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 21. check() call, called by 20.
2 0 0 64 64 64 0
3 0 0 64 0 64 0
4 5 6 7 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 22. check() call, called by 21.
2 0 0 64 64 64 0
3 0 0 8 0 64 0
4 5 6 7 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 23. check() call, called by 22.
2 0 0 9 64 64 0
3 0 0 8 0 64 0
4 5 6 7 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 24. check() call, called by 22.
2 0 0 9 64 64 0
3 0 0 8 0 64 0
4 5 6 7 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 25. check() call, called by 24.
2 0 0 9 10 64 0
3 0 0 8 0 64 0
4 5 6 7 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 26. check() call, called by 24.
2 0 0 9 10 64 0
3 0 0 8 0 64 0
4 5 6 7 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 27. check() call, called by 26.
2 0 0 9 10 11 0
3 0 0 8 0 64 0
4 5 6 7 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 28. check() call, called by 26.
2 0 0 9 10 11 0
3 0 0 8 0 64 0
4 5 6 7 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 29. check() call, called by 28.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 30. check() call, called by 28.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 64 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 31. check() call, called by 30.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 32. check() call, called by 30.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 64 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 33. check() call, called by 32.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 34. check() call, called by 32.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 64 64 64 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 35. check() call, called by 34.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 64 64 15 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 36. check() call, called by 34.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 64 64 15 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 37. check() call, called by 36.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 64 16 15 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 38. check() call, called by 37.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 64 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 39. check() call, called by 38.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 40. check() call, called by 38.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 64 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 41. check() call, called by 40.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 42. check() call, called by 40.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 64 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 43. check() call, called by 42.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 44. check() call, called by 42.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 64 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 45. check() call, called by 44.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 21 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 46. check() call, called by 44.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 21 64
0 0 0 0 0 0 64
1 0 0 0 0 0 0 47. check() call, called by 46.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 21 22
0 0 0 0 0 0 64
1 0 0 0 0 0 0 48. check() call, called by 46.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 21 22
0 0 0 0 0 0 64
1 0 0 0 0 0 0 49. check() call, called by 48.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 50. check() call, called by 37.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 51. check() call, called by 36.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 52. check() call, called by 21.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 53. check() call, called by 20.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 1. trim() call.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 1. trim() pass.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
10 9 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 1. prune() call.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
-1 9 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 2. prune() call, called by 1.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 8 0 18 0 0 0
-1 -1 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 3. prune() call, called by 2.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 7 0 17 16 15 0
0 -1 0 18 0 0 0
-1 -1 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 4. prune() call, called by 3.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 6 0 0 0 14 0
0 -1 0 17 16 15 0
0 -1 0 18 0 0 0
-1 -1 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 5. prune() call, called by 4.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 -1 0 0 0 14 0
0 -1 0 17 16 15 0
0 -1 0 18 0 0 0
-1 -1 0 19 20 21 22
0 0 0 0 0 0 23
1 0 0 0 0 0 0 2. trim() pass.
2 0 0 9 10 11 0
3 0 0 8 0 12 0
4 5 6 7 0 13 0
0 -1 0 0 0 14 0
0 -1 0 17 16 15 0
0 -1 0 18 0 0 0
-1 -1 0 19 20 21 22
0 0 0 0 0 0 23
Maximum recursion depth was 23 calls.
* 0 0 0 0 0 0
* 0 0 * * * 0
* 0 0 * 0 * 0
* * * * 0 * 0
0 1 0 0 0 * 0
0 1 0 * * * 0
0 1 0 * 0 0 0
1 1 0 * * * *
0 0 0 0 0 0 *
Since you said that start and end point must start vertically, I added one extra row for the start and the exit. I didn't need "direction", only the maze and the row and column in it to examine. prune() also needed the exit location, so it wouldn't remove that; otherwise the exits look exactly like dead ends.
The
check() function is the recursive function that checks if the current cell has a step distance that can be reduced (by checking the four neighbours). It is initially called to check the leftmost column in the second row, after the starting point at the top left corner is assigned 1, and all other valid places
N=7×9+1=64.
After a total of 53
check() calls, having maximum recursion depth of 23 calls, we have the minimum number of steps needed to reach the exit, assigned to each valid place in the maze.
The
trim() call scans through the array, until it finds a dead end (a point that is not an exit, but is further from the exit than any of its neighbours). As a dead end, I remove it by assigning it a distance of -1, and calling
prune() on all four neighbours (if they're valid places too, not -1, not exit) to see if any of them now became a dead end.
It is called only once, but it repeats the maze scan until no dead ends are found.
Using signed integers turned out to be nice, as "walls" are zero, and dead ends are similarly uninteresting; putting dead end paths at -1 means everything interesting is positive.
Also, at the beginning of
trim() it does a pass over the entire array, setting all points further than the exit to -1, because they obviously have to be dead ends. This is an optimization, I believe, and in this particular maze it does not matter, as it only shows up when you have a short path from start to exit, and longer dead end paths.
The
prune() function is also recursive. It checks if the specified position in the maze is a dead end, and if so, it is removed by assigning it a distance of -1, and recurses into the four neighbours (if they're valid places too, not -1, not exit), to see if any of them now became a dead end.
The only issue I had when writing the function, was to remember to check that I don't remove the exits. It was obvious, as the trim() removed the exit on the first pass, and then erased the entire path, leaving me with just 0 and -1 entries.